# 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本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-09-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录