算法模板：两个指针 - 第一部分

2020-09-03 08:00飞浪

介绍

正如我们在本系列指南的介绍中了解到的，算法模板展示了算法的核心思想。通过重用和改造这些模板，你可以轻松地将它们应用于新的场景。

在本指南中，我们将重点介绍双指针技术，该技术涉及使用两个指针来跟踪索引、简化逻辑并节省时间和空间。

我们将讨论两个指针的五种变体。对于每种类型，我们将通过两个步骤来了解它：

使用算法模板和流程图描述概念
提供典型示例，帮助您了解应用场景和使用方法

两个指针

指针是 C/C++ 中非常重要的概念，在算法中也同样如此。应用在算法中，指针可以表示序列（如数组或字符串）中的当前元素。我们可以通过组合两个指针以不同的遍历方式来表达复杂的算法逻辑。

双指针技术在很多算法场景中都有广泛的应用，按照机制和用途，我粗略的把它们分为五类：

新旧状态：old,new=new,cur_result
慢跑者和快跑者：慢->快->->
左右边界：|left-> ... <-right|
指针 1 和指针 2 来自两个序列：p1-> p2->
滑动窗口的开始和结束：|start-> ... end->|

上面的列表和下面的概述图以简短而非严谨的方式展示了每种类型的核心思想，只是为了给你一个概述。

在以下章节中，我们将使用代码模板、图表和示例进一步详细讨论每种类型。

慢跑者和快跑者

模板

第一个想法是使用两个指针作为慢速运行器和快速运行器。它们各自标记遍历过程中的一个关键点。一般来说，快速运行器每次迭代都会增长，而慢速运行器会在某些限制下增长。这样，我们就可以根据这两个运行器来处理逻辑。

      # slow & fast runner: slow-> fast->->
def slow_fast_runner(self, seq):
    # initialize slow runner
    slow = seq[0]   # for index: slow = 0
    # fast-runner grows each iteration generally
    for fast in range(seq):     # for index: range(len(seq))
        #slow-runner grows with some restrictions
        if self.slow_condition(slow):
            slow = slow.next    # for index: slow += 1
        # process logic before or after pointers movement
        self.process_logic(slow, fast)

需要注意的是，这个模板只是针对最常见的流程，对于更复杂的场景，比如 fastrunner 也在不断增加一些限制，需要重新改造。理解算法的思路才是最重要的，这样才能举一反三，拓展到更复杂的算法场景。

示例

一个经典的例子是从已排序的数组中删除重复项。我们可以使用快速运行器来表示当前元素，使用慢速运行器来标记新的非重复数组的末尾。

给定一个已排序数组nums，删除重复项，使得每个元素只出现一次，并返回新的长度。

      # [26] https://leetcode.com/problems/remove-duplicates-from-sorted-array/
def removeDuplicates(nums: 'List[int]') -> int:
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        # if current element is not duplicate, 
        # slow runner grows one step and copys the current value
        if nums[slow] != nums[fast]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

再举一个例子，与正常过程不同，跑得快的人比跑得慢的人先跑了一段距离。

给定一个链表，从列表末尾移除第 n 个节点并返回其头。

      # [19] https://leetcode.com/problems/remove-nth-node-from-end-of-list/
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
            
def removeNthFromEnd(head: 'ListNode', n: int) -> 'ListNode':
    dummy = ListNode(0)
    dummy.next = head
    slow, fast = dummy, dummy
	# fast runner moves n step first
    for i in range(n):
        fast = fast.next
    # slow and fast moves together
    while fast.next:
        slow, fast = slow.next, fast.next

    slow.next = slow.next.next
    return dummy.next

旧州与新州

模板

另外一个思路就是用两个指针作为变量，在整个算法过程中，变量存储中间状态，并参与计算产生新的状态。

      # old & new state: old, new = new, cur_result
def old_new_state(self, seq):
    # initialize state
    old, new = default_val1, default_val2
    for element in seq:
        # process current element with old state
        old, new = new, self.process_logic(element, old)
    

为了更好的解释新旧状态的原理，我画了一个状态转换的例子。

从流程图中我们可以看到每次迭代都有三个过程步骤：

根据序列的old_state和cur_element计算cur_result 。
在将cur_result赋值给new_state之前，先将new_state的值存储到old_state中。
将cur_result视为new_state。

遍历整个序列后，根据old_state和new_state计算结果。

就像慢跑者和快跑者一样，这个模板只是代表了典型的用法。上面的模板和流程图可以帮助您理解这个想法。当您迁移到复杂的场景时，您需要进行一些扩展和改革。

示例

一个简单而经典的例子是计算斐波那契数。

每个数字都是前两个数字的总和，从 0 和 1 开始。

      # [509] https://leetcode.com/problems/fibonacci-number/
def fibonacci(n: int) -> int:
	a, b = 0, 1
	for i in range(n + 1):
		a, b = b, a + b
	return a

涉及当前元素的一个例子：

确定您今晚在不抢劫邻近房屋的情况下可以偷走的最大金额。

      # [198] https://leetcode.com/problems/house-robber/
def rob(nums: 'List[int]') -> int:
    last, now = 0, 0
    for i in nums:
        last, now = now, max(last + i, now)
    return now

在更广泛的定义中，我们所维护的这两个变量不一定是前一种状态与后一种状态的关系。

以下是双指针技术的另外两种常见用法。

合并两个已排序的链表并返回一个新列表。

      # [21] https://leetcode.com/problems/merge-two-sorted-lists/
# first make sure that a is the "better" one (meaning b is None or has larger/equal value). Then merge the remainders behind a.
def mergeTwoLists(a: 'ListNode', b: 'ListNode') -> 'ListNode':
    if not a or b and a.val > b.val:
        a, b = b, a
    if a:
        a.next = mergeTwoLists2(a.next, b)
    return a

具有分支逻辑和复杂抽象的更复杂示例：

给定一个仅包含数字的非空字符串，确定解码它的总方法数。

      # [91] https://leetcode.com/problems/decode-ways/
def numDecodings(s: str) -> int:
    if len(s) > 0 and s[0] > '0':
        a, b = 1, 1
    else:
        return 0
    for i in range(1, len(s)):
        if s[i] == '0':
            if s[i - 1] > '2' or s[i - 1] == '0':
                return 0
            a, b = 0, a
        elif s[i - 1] == '1' or (s[i - 1] == '2' and s[i] < '7'):
            a, b = b, a + b
        else:
            a, b = b, b
    return b

从上面的例子可以看出，双指针技术把算法问题的复杂性简化成了状态的定义与变换。

结论

在本指南中，我们学习了一种广泛使用的算法：双指针技术。

首先介绍了该技术的概述和分类，然后通过模板和示例讨论了慢跑者和快跑者以及新旧状态。

在第 2 部分中，我们将继续学习另外两种类型的二叉指针。

要访问完整的代码，你可以从 Github 下载算法模板。我希望其中一些对你有用。

本指南是双指针技术系列指南的一部分：

希望你喜欢。如果您有任何问题，欢迎通过 recnac@foxmail.com 与我联系。

_{免责声明：本内容来源于第三方作者授权、网友推荐或互联网整理，旨在为广大用户提供学习与参考之用。所有文本和图片版权归原创网站或作者本人所有，其观点并不代表本站立场。如有任何版权侵犯或转载不当之情况，请与我们取得联系，我们将尽快进行相关处理与修改。感谢您的理解与支持！}

_查看原文

曝光26604浏览1410