題目名稱
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的異常 複制