Leetcode笔记 每日一题 821. 字符的最短距离（22.04.19）

Leetcode笔记 每日一题 821. 字符的最短距离（22.04.19）

Leetcode 每日一题 821. 字符的最短距离（22.04.19）

题目

给你一个字符串 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 . l e n g t h < = 1 0 4 1 <= s.length <= 10^4 1<=s.length<=104
• s[i] 和 c 均为小写英文字母
• 题目数据保证 c 在 s 中至少出现一次

解题思路 思路一

直接对字符串进行两次遍历
从左往右：当s[l] == c的时候，用x记录一下坐标l，然后计算x-l求出距离
从右往左：当s[r] == c的时候，用x记录坐标r，判断当前位置res[r]和x-r的最小值

Python代码

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n =len(s)
        res = []*n
        x = -n # 由于一开始x不存在，所以假定从左往右的时候 x=-n，方便计算 
        # 从左进行遍历
        for l in range(n):
            if s[l] == c:
                x = l
            res.append(l - x)
        x =2*n # 由于一开始x不存在，所以假定从左往右的时候 x=2*n，方便计算 
        # 从右进行遍历
        for r in range(n-1,-1,-1):
            if s[r] == c:
                x = r
            res[r] = min(res[r],x-r) # 求最小值
        return res

思路二

步骤一 我们可以建立一个列表先标记一下目标字符c和非目标字符ans = [0 if i == c else n for i in s]，当字符i==c的时候距离为0，而其它字符距离最多不会超过z字符串的长度len(s)，所以将目标字符记录为0，非目标字符记录为len(s)，然后从左右两端分别进行计算。
步骤二 从左往右遍历：

如果ans[i] != 0且ans[i-1] != n,那就说明字符i在目标字符c的右侧，所以距离加一

步骤三从右往左遍历：

如果ans[i] != 0 ，ans[i+1] != n,那就说明字符i在目标字符c的左侧，距离加一并与步骤二进行比较，选择最小的值

最后返回列表ans

Python代码

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n = len(s)
        # 标记c
        ans = [0 if i == c else n for i in s] 
        # 从左开始遍历，因为ans[i-1]要存在，所以从第二位开始遍历
        for i in range(1,n):
            if ans[i] != 0 and ans[i-1] != n:
                ans[i] = ans[i-1]+1
        # 从右开始遍历，因为ans[i+1]要存在，所以从倒数第二位开始遍历
        for i in range(n-2,-1,-1):
            if ans[i] != 0 and ans[i+1] != n:
                ans[i] = min(ans[i] , ans[i+1]+1)
        return ans

简便写法

class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        n = len(S)
        res = [0 if c == C else n for c in S]
        for i in range(1, n):
            res[i] = min(res[i], res[i - 1] + 1)
        for i in range(n - 2, -1, -1):
            res[i] = min(res[i], res[i + 1] + 1)
        return res