雙指針問題的演算法
雙指針主要分兩類: 快慢指針和左右指針
快慢指針
對於鏈表問題, 我們一般可以使用快慢指針解決
所謂的快慢指針是指, 使用兩個指針按照不同的速度前進, 有兩個指針我們可以確定:
- 鏈表是否有環
- 鏈表的倒數第k個節點
一些題目
比如: 141題環形鏈表
注意: 兩個指針相遇則有環 (類比在操場跑步, 速度不相等總能相遇)
程式碼
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head:
return False
fast_node = head.next
slow_node = head
while fast_node and fast_node.next:
if slow_node == fast_node:
return True
fast_node = fast_node.next.next
slow_node = slow_node.next
return False
又比如:
左右指針
左右指針一般的形式就是我們常說的二分查找(二分搜索)
一般的使用方式:
def binary_search(nums: List[int], target: int):
left = 0
right = ...
while ...:
mid = left + (right - left) / 2
if nums[mid] == target:
...
elif nums[mid] < target:
left = ...
elif nums[mid] > target:
right = ...
return ...
我們需要的注意點為...部分:
- 前兩個
...有由搜索區間決定, 即問題為[left : right]或[left : right)
[left: right]:right = len(nums) - 1和while left <= right
[left: right):right = len(nums)和while left < right
前者的結束條件為:[right + 1 : right](如:[3 : 2])
後者的結束條件為:[left : right](如:[2 : 2]) - 後面的
...由題目決定
nums[mid] == target: 返回某個值的問題, 直接返回; 返回邊界的問題, 縮小邊界(right = mid或left = mid)
nums[mid] > target: 太大了, 一般為縮小右邊界:right = mid - 1
nums[mid] < target: 太小了, 一般為縮小左邊界:left = mid + 1
對於一些問題, 我們可以將問題的區間統一為[left : right], 即right = len(nums) - 1和while left <= right
比如:
返回某個值的問題
def binary_search(nums: List[int], target: int):
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
# 直接返回
return mid
return -1
在leetcode上對應的題目:704.二分查找（簡單） 題解
返回左邊界的問題
def left_bound(nums: List[int], target: int):
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
# 別返回，鎖定左側邊界
right = mid - 1
# 最後要檢查 left 越界的情況
# left可能超出範圍 即 >= len(nums)
if left >= len(nums) or nums[left] != target:
return -1
return left
結束條件為:
[right + 1 : right](如:[3 : 2])
返回左邊界left
返回右邊界的問題
def right_bound(nums: List[int], target: int):
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
# 別返回，鎖定右側邊界
left = mid + 1
# 最後要檢查 right 越界的情況
if right < 0 or nums[right] != target:
return -1
return right
結束條件為:
[right + 1 : right](如:[3 : 2])
返回右邊界right
在leetcode上對應的題目:
滑動窗口
滑動窗口是雙指針的一種, 也可以說是左右指針的一種
其主要解決的是子串問題
所謂的子串問題是指: 一個長的字元串是否全部包含 一個短的字元串 (包括數量)
滑動窗口的思想:
① 我們可以設兩個指針, 分別對應窗口的左右邊界
② 右邊界向右擴大窗口, 直到找到符合條件的子串
③ 左邊界向右縮小窗口, 更新數據, 根據題目是否返回
④ 假如還未返回, 則重複②和③
⑤ 根據題目是否返回
模板:
def sliding_window(s: str, t: str):
"""
:param s 大的字元串
:param t 小的字元串
:return 根據題目返回
"""
need = {} # 存放需要的字元數
windows = {} # 存放當前窗口中的字元數
# 記錄需要的字元數
for char in t:
# 需要字元的數量自增1
need[char] = need.setdefault(char, 0) + 1 # setdefault作用字典中不存在字元時, 返回0
# 左右邊界的指針
left = right = 0
# 用於記錄已經通過檢驗的字元數
valid = 0
"""
假如有其他變數可以在這裡添加
"""
while right < len(s):
# right_char為將要移入的窗口字元
right_char = s[right]
# 右移窗口
right += 1
# 假如當前 右邊界 的字元,為需要的字元
if right_char in need:
"""
更新數據
一般是
1. 當前窗口的數據
2. 通過的 字元數
"""
# 記錄當前窗口符合要求的字元數量
windows[right_char] = windows.setdefault(right_char, 0) + 1
# 假如當前字元已經符合要求
# 通過檢驗的字元數 + 1
if windows[right_char] == need[right_char]:
valid += 1
# 判斷左邊界是否可以收縮
# !!!! 這個條件根據題目而變
while condition:
"""
根據題目是否在這裡返回
"""
# left_char為將要移出的窗口字元
left_char = s[left]
left += 1
if left_char in need:
""""
更新數據
一般是
1. 當前窗口的數據
2. 通過的 字元數
自定義的其他變數也在這裡更新
"""
# 假如當前字元已經符合要求
# 通過檢驗的字元數 - 1
if windows[left_char] == need[left_char]:
valid -= 1
# 記錄當前窗口符合要求的字元數量 - 1
windows[left_char] = windows.setdefault(left_char, 0) - 1
"""
根據題目是否在這裡返回
"""
這個模板的主要注意點是
- 是否需要一些其他的變數, 如當前子串的長度
- 邊界縮小的條件
- 什麼時候返回
