专栏首页用户2133719的专栏常见编程模式之快慢指针

常见编程模式之快慢指针

3. 快慢指针(Fast & Slow pointers)

基本原理及应用场景

快慢指针方法,又称为龟兔赛跑算法,其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理「环形」链表或数组非常有用。以链表为例,通过以不同的速度移动,我们可以证明如果链表中存在环,则两个指针必定会相遇,当两个指针均处在环中时,快指针会追上慢指针(如下图所示)。

在以下场景中,我们可能会用到快慢指针:

  • 题目涉及包含「循环」的链表或数组
  • 需要求解链表中某个元素的位置或链表长度

快慢指针和双指针比较类似(可以理解为特殊的双指针法),在只能单向移动的数据结构中(如单向链表),一般使用快慢指针,如判断回文链表(Leetcode 234)。

经典例题

141. 环形链表(Easy)

给定一个链表,判断链表中是否有环。

「示例」

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

采用快慢指针,快指针每次向前两步,慢指针每次向前一步,只有链表中存在环时两指针才会相遇:

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow, fast = head, head
        while fast and fast.next: # 只要关注fast即可
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                return True
        return False

该方法的证明如下:

  • 如果快指针在慢指针后一格,则下一步快指针移动两格,慢指针移动一格,两者相遇;
  • 如果快指针在慢指针后两格,则下一步后快指针在慢指针后一格,回到第一种情况,两者可以相遇
  • 如果快指针在慢指针后 N 格,则下一步后快指针在慢指针后 N - 1 格,根据上述情况,两者必会相遇

可以看到快指针追赶慢指针是一个递归的过程,只要存在循环,则两者必然会在某一时间点相遇。

142. 环形链表 II(Medium)

给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null

「示例」

输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。

这道题基本思路与上一题一样,先到达快慢指针相等的位置,然后新建一个指针从头开始移动,直到和慢指针相遇的位置即为循环起始节点:

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                current = head
                while current != slow:
                    current = current.next
                    slow = slow.next
                return slow
        return None

下面简单证明上述方法的正确性。如下图所示,假定快慢指针在节点 「-4」 处相遇,则快指针走过的距离为 A+2B+C,慢指针走过的距离为 A+B。由于快指针的速度为慢指针的两倍,所以我们有 A+2B+C == 2(A+B),从而得到 A == C。因此,我们再使用另一个指针从头结点开始移动(每次一步),此时慢指针也同时移动,则两者必会在节点 「2」 相遇,即循环开始的点。

457. 环形数组循环(Medium)

给定一个含有正整数和负整数的「环形」数组 nums。如果某个索引中的数 k 为正数,则向前移动 k 个索引。相反,如果是负数 (-k),则向后移动 k 个索引。因为数组是环形的,所以可以假设最后一个元素的下一个元素是第一个元素,而第一个元素的前一个元素是最后一个元素。 确定 nums 中是否存在循环(或周期)。循环必须在相同的索引处开始和结束并且循环长度 > 1。此外,一个循环中的所有运动都必须沿着同一方向进行。换句话说,一个循环中不能同时包括向前的运动和向后的运动。

「示例 1」

输入:[2,-1,1,2,2]
输出:true
解释:存在循环,按索引 0 -> 2 -> 3 -> 0 。循环长度为 3 。

「示例 2」

输入:[-1,2]
输出:false
解释:按索引 1 -> 1 -> 1 ... 的运动无法构成循环,因为循环的长度为 1 。根据定义,循环的长度必须大于 1 。

这道题可以通过快慢指针法解决。由于题目明确数组元素不为 0,我们可以通过将元素置 0 来标记已经遍历过的元素,以减少时间复杂度。这里的快慢指针选择从不同起点开始移动,因为指针的更新位于内循环的最后。对于不同的题目,需要根据实际情况选择指针的起始位置和循环的终止条件,本题中的终止条件为快慢指针所指向的操作不同向(注意由于快指针一次移动两步,所以还需要和当前快指针对应的下一个元素的操作比较)。具体的代码实现如下:

class Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        def getNext(i): # 求出下一个位置
            return (nums[i] + i) % n
        
        n = len(nums)
        for i in range(n):
            if nums[i] == 0: continue # 用0标记已访问的元素,实现剪枝
            slow, fast = i, getNext(i) # 设定快慢指针,慢指针指向当前索引,快指针指向下一个索引(这里起始两指针位置不同)
            # 保证快慢指针同向且慢指针和快指针的下一个也同向(因为快指针一次移动两步)
            while nums[slow] * nums[fast] > 0 and nums[slow] * nums[getNext(fast)] > 0:
                if slow == fast:
                    if slow == getNext(slow):
                        break
                    return True
                slow = getNext(slow)
                fast = getNext(getNext(fast))
            # 对于已经遍历过的节点置0,因为其对应的序列不可能存在合法循环了,否则已经返回True了(剪枝)
            slow = i
            val = nums[i]
            while val * nums[slow] > 0:
                nums[slow] = 0
                slow = getNext(slow)
        return False

其他类似的题目列表:

  • LeetCode 202-「快乐数」(Easy)
  • LeetCode 234-「回文链表」(Easy)
  • LeetCode 876-「链表的中间节点」(Easy)

本文分享自微信公众号 - 口仆(roito33),作者:口仆

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 卡特兰数入门

    括号的合法匹配方式为:一个左括号对应一个右括号,且左括号必须要在右括号前面出现。为了方便说明,这里将左括号记作 +1,右括号记作 -1,则一个合法序列和一个非法...

    口仆
  • 知识图谱入门(二)

    本节我们将介绍数据图的各种增强与扩展,包括「模式」(schema)、「身份」(identity)和「上下文」(context),它们为知识的聚合提供了额外的结构...

    口仆
  • 常见编程模式之双指针

    双指针模式指使用两个一前一后的指针遍历数据结构,直到某个指针触发停止条件。该模式常用于在有序数组或链表中搜索元素对。使用双指针的好处在于和单指针相比,不用去连续...

    口仆
  • 142. Linked List Cycle II

    首先要证明链表有环: 用快慢两个指针解决。快指针每次走两步,慢指针每次走一步。如果有环,则一定会最终在环内某点相遇。下面证明这一点:

    平凡的学生族
  • Golang语言--指针

    在Go中指针是很容易学习的。一些进入编程任务,指针更容易操作,如通过引用调用,需要要使用指针来执行。所以学习指针成为完美Go程序员很有必要。让我们开始学习指针的...

    李海彬
  • 怎样熟练掌握C语言的指针?

    从事C语言开发已经超过10个年头,越来越觉得指针的方便之处,但在初学者来看指针就是拿下这门编程最大的拦路虎,毕竟很多人开始学习C语言都是激情四射结果遇上了指针猫...

    程序员互动联盟
  • 空指针 到底是什么意思?

    各位,前段时间我们有推文介绍过野指针和悬空指针,那C中还有一个叫做空指针的名词,它究竟是指什么呢,今天就跟大伙聊聊这个空指针。

    7089bAt@PowerLi
  • 视频流媒体平台编译中如何运用Go语言指针?

    本文讲的也是我们在编译流媒体平台EasyNVR的时候,碰到的go语言指针问题,就打算为大家介绍一下Go语言指针的运用。

    EasyNVR
  • 基础知识 | 每日一练(59)

    士人有百折不回之真心,才有万变不穷之妙用。立业建功,事事要从实地着脚,若少慕声闻,便成伪果;讲道修德,念念要从虚处立基,若稍计功效,便落尘情。 ...

    C语言入门到精通
  • LeetCode | 使用双指针解决11号题

    第4题号还有二分查找和分治算法,算法比较复杂。那我就接着做下一道题号,第11题号。

    我脱下短袖

扫码关注云+社区

领取腾讯云代金券