双指针问题的算法
双指针主要分两类: 快慢指针和左右指针
快慢指针
对于链表问题, 我们一般可以使用快慢指针解决
所谓的快慢指针是指, 使用两个指针按照不同的速度前进, 有两个指针我们可以确定:
- 链表是否有环
- 链表的倒数第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
"""
根据题目是否在这里返回
"""
这个模板的主要注意点是
- 是否需要一些其他的变量, 如当前子串的长度
- 边界缩小的条件
- 什么时候返回
