Double pointers are mainly divided into two categories: fast and slow pointers and left and right pointers
Speed pointer
For the linked list problem, we can generally use the speed pointer to solve it
The so-called speed pointer refers to using two pointers to advance at different speeds. There are two pointers that we can determine:
- Is there a link in the linked list
- The penultimate node of the lin k ed list
Some topics
For example: Circular linked list of 141 questions
Note: when two pointers meet, there is a ring (similar to running on the playground, if the speed is not equal, they can always meet)
code
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
Another example:
Left and right pointer
The general form of left and right pointers is what we often call binary search (binary search)
General usage:
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 ...
What we need to pay attention to is part:
- The first two Yes, it is determined by the search interval, that is, the problem is [left: right] or [left: right]
[left: right]: right = len(nums) - 1 and while left < = right
[left: right): right = len(nums) and while left < right
The end condition of the former is: [right + 1: right] (for example: [3: 2])
The end condition of the latter is: [left: right] (for example: [2: 2]) - hinder... Determined by the subject
nums[mid] == target: the problem of returning a certain value is returned directly; Return to the problem of boundary, narrow the boundary (right = mid or left = mid)
Num [mid] > target: too large, usually to narrow the right boundary: right = mid - 1
Num [mid] < target: too small, usually to narrow the left boundary: left = mid + 1
For some problems, we can unify the interval of the problem as [left: right], that is, right = len (Num) - 1 and while left < = right
For example:
Problem of returning a value
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:
# Direct return
return mid
return -1
Corresponding questions on leetcode: 704. Binary search (simple) Problem solution
Problem of returning to the left boundary
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:
# Don't go back, lock the left boundary
right = mid - 1
# Finally, check the left crossing
# left may be out of range, i.e. > = len (nums)
if left >= len(nums) or nums[left] != target:
return -1
return left
The end condition is: [right + 1: right] (for example: [3: 2])
Return left border
Problem of returning to the right boundary
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:
# Don't go back, lock the right boundary
left = mid + 1
# Finally, check the right crossing
if right < 0 or nums[right] != target:
return -1
return right
The end condition is: [right + 1: right] (for example: [3: 2])
Return to right boundary
Corresponding questions on leetcode:
- 707. Find the first and last positions of elements in the sorted array (medium)
- Find the solution of the first and last position of the element in the sorted array
sliding window
Sliding window is a kind of double pointer, which can also be said to be a kind of left and right pointers
It mainly solves the substring problem
The so-called substring problem refers to whether a long string contains a short string (including quantity)
Idea of sliding window:
① We can set two pointers corresponding to the left and right boundaries of the window
② The right boundary expands the window to the right until a qualified substring is found
③ Narrow the window from the left border to the right, update the data, and return according to the title
④ If not, repeat ② and ③
⑤ Whether to return according to the topic
Template:
def sliding_window(s: str, t: str):
"""
:param s Large string
:param t Small string
:return Return according to the topic
"""
need = {} # Number of characters required for storage
windows = {} # Number of characters stored in the current window
# Record the number of characters required
for char in t:
# The number of characters required increases by 1
need[char] = need.setdefault(char, 0) + 1 # setdefault returns 0 when there are no characters in the dictionary
# Pointer to left and right boundary
left = right = 0
# Used to record the number of characters that have passed the inspection
valid = 0
"""
If there are other variables, you can add them here
"""
while right < len(s):
# right_char is the character of the window to be moved in
right_char = s[right]
# Move window right
right += 1
# If the character of the current right boundary is the required character
if right_char in need:
"""
Update data
Generally
1. Data of current window
2. Number of characters passed
"""
# Record the number of characters that meet the requirements of the current window
windows[right_char] = windows.setdefault(right_char, 0) + 1
# If the current character already meets the requirements
# Number of characters passed + 1
if windows[right_char] == need[right_char]:
valid += 1
# Determine whether the left boundary can shrink
# !!!! This condition varies according to the subject
while condition:
"""
According to whether the title is returned here
"""
# left_char is the character of the window to be moved out
left_char = s[left]
left += 1
if left_char in need:
""""
Update data
Generally
1. Data of current window
2. Number of characters passed
Other customized variables are also updated here
"""
# If the current character already meets the requirements
# Number of characters passed - 1
if windows[left_char] == need[left_char]:
valid -= 1
# Record the number of characters that meet the requirements of the current window - 1
windows[left_char] = windows.setdefault(left_char, 0) - 1
"""
According to whether the title is returned here
"""
The main points to note about this template are
- Do you need some other variables, such as the length of the current substring
- Conditions for boundary reduction
- When will you return