算法模板：两个指针 - 第二部分
本指南继续讨论双指针对话，并介绍了该算法模板技术的两个更重要的变体。
介绍
这是算法模板系列文章的第二部分：两个指针。在第一部分中，我们深入研究了两个指针技术的前两种类型。如果你错过了，请查看。
在本指南（第 2 部分）中，我们将重点介绍另外两种常见用法：
- 左右边界
- 来自两个序列的指针 1 和指针 2
对于每一种类型，我们将通过两个步骤来了解它：
- 通过算法模板和流程图描述概念
- 提供典型示例，帮助您了解应用场景和使用方法
左右边界
模板
另一种常见用法是将指针放在最左侧和最右侧。一个指针从头开始，而另一个指针从尾开始。它们相互靠近，直到在中间相遇。
# left & right boundary: left-> <-right
def left_right_boundary(self, seq):
left, right = 0, len(seq) - 1
while left < right:
# left index moves when satisfy the condition
if self.left_condition(left):
left += 1
# right index move when satisfy the condition
if self.right_condition(right):
right -= 1
# process logic before or after pointers movement
self.process_logic(left, right)
为了更好地理解左右边界的理论，您可以参考下面的示例图表。
总体来说，基于该技术算法可以有两种使用方式：
- 左指针和右指针形成一个区间来处理。
- 这两个指针携带信息并处理每次迭代中的逻辑。
示例
最经典、最著名的例子就是二分查找，通过不断缩小上下界来找到目标，每次迭代都会截断一半的区间，下面这个例子就是同时包含上下界的版本。
# [lo, hi] version, modify to [lo, hi) version as you need
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
# find the target, change to your comparison condition as you need
if arr[mid] == target:
break
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
让我们看一个具有两个指针和二分搜索技术的实际例子。
给定一个已经按升序排序的整数数组，找到两个数字，使得它们加起来等于特定的目标数字。
# [167] https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
def twoSum(numbers: 'List[int]', target: 'int') -> 'List[int]':
left, right = 0, len(numbers) - 1
while left < right:
if numbers[left] + numbers[right] == target:
return [left + 1, right + 1]
if numbers[left] + numbers[right] < target:
left += 1
else:
right -= 1
return [0, 0]
让我们让它稍微困难一些。将二和问题升级为四和问题。
找出数组中所有唯一的四元组，得出目标的总和。
思路：通过上面的例子，解法就很清晰了，可以利用左右边界来寻找解空间，可以把四和问题分解成三和问题，最后分解成二和问题。
# [18] https://leetcode.com/problems/4sum/
def fourSum(nums: 'List[int]', target: int) -> 'List[int]':
result, n = [], len(nums)
if n < 4: return result
nums = sorted(nums)
if sum(nums[-4:]) < target:
return result
for i in range(n - 3):
# boundary checker, stop early
if sum(nums[i:i + 4]) > target:
break
# right boundary checker
if nums[i] + sum(nums[-3:]) < target:
continue
# skip same element, but keep the first one
if i > 0 and nums[i] == nums[i - 1]:
continue
# simplify the problem to three sum
target2 = target - nums[i]
for j in range(i + 1, n - 2):
if sum(nums[j:j + 3]) > target2 or sum(nums[-3:]) < target2:
break
if nums[j] + sum(nums[-2:]) < target2:
continue
if j > i + 1 and nums[j] == nums[j - 1]:
continue
# simplify the problem to two sum
target3 = target2 - nums[j]
left = j + 1
right = n - 1
while left < right:
if nums[left] + nums[right] == target3:
result.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif nums[left] + nums[right] < target3:
left += 1
else:
right -= 1
return result
下面是一个我们重点关注间隔的例子。
找到两条线，与 x 轴一起形成一个容器，使得容器中装有尽可能多的水。
思路：为了方便大家理解，我画了一个示例图，通过当前左右边界形成的区间来计算水域面积。
# [11] https://leetcode.com/problems/container-with-most-water/
def maxArea(height: 'List[int]') -> int:
left, right = 0, len(height) - 1
area_max = (right - left) * min(height[left], height[right])
while left < right:
# judge which side decide the area (shorter height)
if height[left] <= height[right]:
last_height = height[left]
# skip all the height less than current
while height[left] <= last_height and left < right:
left += 1
else:
last_height = height[right]
# skip all the height less than current
while height[right] <= last_height and left < right:
right -= 1
if left >= right:
return area_max
area_max = max(area_max, (right - left) * min(height[left], height[right]))
return area_max
来自两个序列的指针 1 和指针 2
模板
在其他一些场景中，我们需要在两个序列中进行比较。每个指针代表相应序列中的当前逻辑位置。
# p1 & p2 from two sequences: p1-> p2->
def pointers_from_two_seq(self, seq1, seq2):
# init pointers
p1, p2 = 0, 0 # or seq1[0], seq2[0]
# or other condition
while p1 < len(seq1) and p2 < len(seq2):
# p1 index moves when satisfy the condition
if self.p1_condition(p1):
p1 += 1 # or p1 = next(seq1)
# p2 index move when satisfy the condition
if self.p2_condition(p2):
p2 += 1 # or p2 = next(seq2)
# process logic before or after pointers movement
self.process_logic(p1, p2)
从下面的示例图中我们可以看出，这两个指针是相对独立的，它们如何前进是由各自的策略决定的。
示例
让我们看一个包含多个序列的例子。
设计一个类，在构造函数中接收一个单词列表，并实现一个方法，该方法接受两个单词word1和word2，并返回列表中这两个单词之间的最短距离。
思路：首先我们为每个单词创建一组索引序列locations。每次调用shortest函数时，我们都会取出相应的序列loc1和loc2。然后我们使用两个指针l1和l2来计算最短距离。在每次迭代中，较小的指针向前移动一步。
# [244] https://leetcode.com/problems/shortest-word-distance-ii/
class WordDistance:
def __init__(self, words: 'List[str]'):
self.locations = defaultdict(list)
# Prepare a mapping from a word to all it's locations (indices).
for i, w in enumerate(words):
self.locations[w].append(i)
def shortest(self, word1: str, word2: str) -> int:
loc1, loc2 = self.locations[word1], self.locations[word2]
l1, l2 = 0, 0
min_diff = float("inf")
# Until the shorter of the two lists is processed
while l1 < len(loc1) and l2 < len(loc2):
min_diff = min(min_diff, abs(loc1[l1] - loc2[l2]))
if loc1[l1] < loc2[l2]:
l1 += 1
else:
l2 += 1
return min_diff
下面是与回溯相结合的另一个例子。
给定一个输入字符串 (s) 和一个模式 (p)，实现支持“？”和“*”的通配符模式匹配。
思路：将一个指针s_cur指向目标字符串，另一个指针p_cur指向模式，两个指针记录当前匹配的位置，在匹配'*'时，match和star是贪婪算法中匹配失败时用来回溯的标志位。
# [44] https://leetcode.com/problems/wildcard-matching/
def isMatch(s: str, p: str) -> bool:
s_cur, p_cur, match, star = 0, 0, 0, -1
while s_cur < len(s):
# match sucess, both two pointers move forward
if p_cur < len(p) and (s[s_cur] == p[p_cur] or p[p_cur] == '?'):
s_cur += 1
p_cur += 1
# if matching star, record current state and try to match in greedy
elif p_cur < len(p) and p[p_cur] == '*':
match = s_cur
star = p_cur
p_cur += 1
# backtrack if match failed
elif star != -1:
p_cur = star + 1
match += 1
s_cur = match
else:
return False
# corner case: remove continuous star in the rest
while p_cur < len(p) and p[p_cur] == '*':
p_cur += 1
if p_cur == len(p):
return True
else:
return False
结论
免责声明：本内容来源于第三方作者授权、网友推荐或互联网整理，旨在为广大用户提供学习与参考之用。所有文本和图片版权归原创网站或作者本人所有，其观点并不代表本站立场。如有任何版权侵犯或转载不当之情况，请与我们取得联系，我们将尽快进行相关处理与修改。感谢您的理解与支持！
阅读全文
请先 登录后发表评论 ~