＃ Leetcode 821. 字符的最短距离(简单)

题目名称

821. 字符的最短距离

自己想的解法

题目思路

• 遍历一遍字符串ｓ，获取记录预期字符ｃ在ｓ中所有位置的列表 list_c
• 定义一个方法: 获取输入字符 和 列表中所有元素 所有差值中绝对值最小的那个值
• 遍历字符串s，每遍历到一个字符时，调用一次自定义方法，记录到数组中

code for Python3

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        list_c = [i for i in range(len(s)) if s[i] == c]
        arr = []
        for j in range(len(s)):
            arr.append(self.get_abs_minnum(j, list_c))
        return arr

    def get_abs_minnum(self, first_num:int, li:List):
        cur = pow(10, 4)
        for v in li:
            cur = min(cur, abs(v - first_num))
        return cur

复制

复杂度分析

• 时间复杂度: O(N²) 　　原因: 双层循环, 每次遍历字符串s时,都会遍历一次list_c
• 空间复杂度: O(N) 　　原因: list_c占用的空间大小和字符串s的长度有关

官方题解

仔细研究了一下官方题解, 发现思路特别的巧妙, 其思路值得借鉴!

题目思路

• 先从左到右遍历一次S, 记录当前字符与C距离的绝对值.在未出现预期值前,该位置用正无穷替代;出现预期值后,记录实际距离
• 从右往左遍历一次S,同样的 记录当前字符与C距离的绝对值.
• 在第2次遍历过程中, 取当前遍历结果的绝对值 与 第1次遍历值 的最小值,添加到数组中

code for Python3

class Solution(object):
    def shortestToChar(self, S, C):
        prev = float('-inf')
        arr = []
        for i, x in enumerate(S):
            if S[i] == C:
                prev = i
            else:
                arr.append(i - prev)
                
        prev = float('inf')
        for i in range(len(S) -1, -1, -1):
            if S[i] == C:
                prev = i
            else:
                arr.append(min(prev-i, arr[i]))
        return arr

复制

复杂度分析

• 时间复杂度: O(N) 　　原因: 仅遍历了2次字符串S
• 空间复杂度: O(N) 　　原因: arr数组的长度

python的相关知识

• enumerate 方法: 在输出数据结构的索引 和 值的时候使用

s = "abcdefg"
for i, j in enumerate(s):
    print(i, j)

结果为:
0 a
1 b
2 c
3 d
4 e
5 f
6 g

--------------------------------------------------

for k in enumerate(s):
    print(k)

结果为:
(0, 'a')
(1, 'b')
(2, 'c')
(3, 'd')
(4, 'e')
(5, 'f')
(6, 'g')

复制

• 关于python中的无穷大, 无穷小

定义无穷大: float('inf')
定义无穷小: float('-inf')

特殊情况:
0*无穷大 or 0*无穷小   结果为nan(不是一个数, 所有和nan的相关计算都无法获取结果)

其它的示例:
float('nan') + 9999999   # nan
float('nan') - 9999999   # nan
float('nan') * 9999999   # nan

0 - 无穷小 -> 无穷大
0 - float('-inf')   # float('inf')

复制

• 列表的倒序输出

s = [1,2,3,4,5]
for i in range(len(s) - 1, -1, -1):
  print(s[i])

结果为:
5
4
3
2
1

复制