leetcode 821. 字符的最短距离

leetcode 821. 字符的最短距离.

题目描述

821. 字符的最短距离

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。

返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。

两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。

示例 1：

输入：s = "loveleetcode", c = "e" 输出：[3,2,1,0,1,0,0,1,2,2,1,0] 解释：字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。 距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。 距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。 对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。 距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 。 示例 2：

输入：s = "aaab", c = "b" 输出：[3,2,1,0]

提示： 1 <= s.length <= 104 s[i] 和 c 均为小写英文字母 题目数据保证 c 在 s 中至少出现一次

解题思路

法1

方法1:取最佳

我们来回遍历两次字符串,一次从左往右,一次从右往左,取最小的结果储存到数组中并返回数组的值

首先创建了一个与字符串 s 长度相同的整数数组 ans，用于存储每个位置到最近的字符 c 的距离。

接下来，代码使用两次遍历来计算距离。第一次遍历从左到右，维护一个变量 prev，表示最近的字符 c 的索引。如果当前位置的字符等于 c，则更新 prev 为当前索引，否则计算当前位置到 prev 的距离并存储到 ans 数组中。

第二次遍历从右到左，同样维护一个变量 prev，表示最近的字符 c 的索引。如果当前位置的字符等于 c，则更新 prev 为当前索引，然后计算当前位置到 prev 的距离，并与第一次遍历得到的距离比较，取较小值存储到 ans 数组中。

最后，返回计算得到的 ans 数组作为结果。

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

func shortestToChar(s string, c byte) []int {
    n := len(s)
    ans := make([]int, n)

    prev := -n
    for i := 0; i < n; i++ {
        if s[i] == c {
            prev = i
        }
        ans[i] = i - prev
    }

    prev = 2 * n
    for i := n-1; i >= 0; i-- {
        if s[i] == c {
            prev = i
        }
        ans[i] = min(ans[i], prev - i)
    }

    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 2.2 MB , 在所有 Go 提交中击败了 100.00% 的用户 通过测试用例： 76 / 76 炫耀一下: