题目名称
821. 字符的最短距离
理解
个人觉得昨天的这个题很经典.大家可以此题为基础练习多种算法思想, 为以后学习算法打基础.参考其它大佬的解法, 整理了2个不错的思路, 方便大家参考.
中心扩展法
题目思路
- 每次遍历到一个变量时, 从该位置定义2个指针, 分别向左, 右遍历.计算2个位置到初始位置距离的最小值
- 将该最小值记录到数组中
code for Python3
class Solution:
def shortestToChar(self, s: str, c: str) -> List[int]:
# 中心扩展法
len_s = len(s) - 1
arr = []
for i in range(len(s)):
shortest = float('inf')
if s[i] == c:
arr.append(0)
continue
else:
left, right = i, i
while left >= 0:
if s[left] == c:
shortest = min(shortest, i - left)
break
else:
left -= 1
while right <= len_s:
if s[right] == c:
shortest = min(shortest, right - i)
break
else:
right += 1
arr.append(shortest)
return arr
复制
复杂度分析
- 时间复杂度: O(N²)
-
空间复杂度: O(1)
此处使用的是额外空间复杂度, 不考虑返回结果占用的空间!
滑动窗口法
题目思路
- 以预期字符串c为临界点, 划分为很多个窗口
- 遍历s中字符时, 分别计算当前字符与所在窗口左右边界点的距离,取最小值放到数组中
code for Python3
class Solution:
def shortestToChar(self, s: str, c: str) -> List[int]:
# 滑动窗口法
arr = []
left = float('-inf')
right = s.find(c)
for i in range(len(s)):
if i == right:
# 更新窗口
left = right
right = s.find(c, right + 1)
if s[i] == c:
arr.append(0)
continue
else:
# 加了个判断, 如果right = -1,即最后一个窗口的右边界为字符串长度时, 此时的最小距离为当前字符与左边界的距离!
arr.append(min(i - left, right - i)) if right != -1 else arr.append(i - left)
return arr
复制
- 时间复杂度: O(N) N为字符串S的长度
-
空间复杂度: O(1)
此处使用的是额外空间复杂度, 不考虑返回结果占用的空间!
python的相关知识
- 字符串中查找元素
# find()方法
s = "abcdefb"
print(s.find("b")) # 1
print(s.find("b", 2)) # 6 从指定位置后, 查询下一个字符串
print(s.find("k")) # -1
# index方法
s = "abcdefb"
print(s.index("b")) ## 1
print(s.index("b", 2)) # 6
print(s.index("k")) # ValueError: substring not found
可见, find 和 index 使用方法基本相同
相同点
1.都可以查找字符串中第一个出现的字符
2.都可以指定从某一个索引后面开始, 查找下一个出现的字符
不同点
1.find 找不到元素时,会返回-1
2.index 找不到元素时, 会返回 ValueError
复制
- 列表中查找元素
s = ['a', 'b', 'c', 'd', 'e', 'f', 'b']
print(s.index("b"))
print(s.index("b", 2)) # 6
注意
1.list中查找元素,只能使用index, 无find方法.
2.查找不到元素时, 一样会出现 ValueError的异常 复制