破解编码面试：快慢指针技术部分-js教程-PHP中文网

破解编码面试：快慢指针技术部分

花韻仙語

发布： 2024-10-17 10:10:04

转载

479人浏览过

破解编码面试：快慢指针技术部分

在深入研究下一个技术之前，如果您正在准备编码面试并想要全面的资源，请务必探索破解编码面试的十大必备书籍（从初级到高级排名）。对于任何决心在顶级科技公司找到工作的人来说，这都是一本必备的书。

快指针和慢指针技术概述

快慢指针技术（也称为弗洛伊德龟兔赛跑）是一种优雅而有效的模式，用于解决涉及链表和数组等数据结构中的循环问题。这个想法是使用两个以不同速度移动的指针。通常，一个指针（“快”指针）一次移动两步，而另一个指针（“慢”指针）一次移动一步。这使您可以有效地检测循环，找到链表的中间，并解决涉及序列中的重复模式或中间点的各种其他问题。

何时使用快指针和慢指针：

问题涉及在链表或数组中查找循环。
你需要判断一个链表是否有环，并找到该环的起始节点。
要求您一次性找到链表的中间元素。
问题涉及循环模式或重复序列。

快、慢指针技术应用

1. 检测链表中的循环

它是什么：这是快慢指针方法解决的经典问题。如果链表包含环，则快指针最终会遇到慢指针，从而确认环的存在。

示例问题：给定一个链表，确定它是否包含循环。

class listnode:
    def __init__(self, value=0, next=none):
        self.value = value
        self.next = next

def has_cycle(head):
    slow, fast = head, head

    while fast and fast.next:
        slow = slow.next  # move slow by 1 step.
        fast = fast.next.next  # move fast by 2 steps.

        if slow == fast:
            return true  # cycle detected.

    return false  # no cycle detected.

登录后复制

说明：

慢指针每次移动一步，快指针移动两步。
如果存在循环，快指针最终会追上慢指针，确认循环的存在。
如果快指针到达链表末尾，则表示不存在循环。

2. 在链表中查找循环的开始

它是什么：一旦在链表中检测到循环，另一个常见问题是找到循环的起始节点。这可以通过将其中一个指针重置到头部并将两个指针一次移动一步来完成。他们将在周期开始时见面。

示例问题：给定一个有循环的链表，找到循环开始的节点。

def find_cycle_start(head):
    slow, fast = head, head
    cycle_exists = false

    # first, determine if a cycle exists.
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            cycle_exists = true
            break

    if not cycle_exists:
        return none  # no cycle found.

    # reset one pointer to the head and move both at the same speed.
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow  # this is the start of the cycle.

登录后复制

说明：

检测到一个循环后，将一个指针重置到头部，并一次移动两个指针（慢速和快速）。
它们相遇的点就是循环的起始节点。

3. 查找链表的中间位置

它是什么：快慢指针技术也可以用于在单次遍历中找到链表的中间元素。

示例问题：给定一个链表，找到中间节点。

def find_middle(head):
    slow, fast = head, head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow  # slow will be at the middle when fast reaches the end.

登录后复制

说明：

快指针每次移动两步，慢速指针一次移动一步。
当快指针到达列表末尾时，慢指针将位于列表的中间。

快指针和慢指针技术的主要优点

效率：这种方法消除了多次遍历数据结构的需要。相反，它只需一次即可处理大多数问题，使其时间复杂度o(n)。
简单： 只需两个指针和一些条件，就避免了嵌套循环的复杂性。
多功能性：它可以应用于涉及循环、中间元素或检测链表和数组中的重复模式的各种问题。

使用快指针和慢指针的常见面试问题

1. 链表循环检测

问题：给定一个链表，确定它是否包含循环。
解决方案：使用快慢指针方法来检测两个指针是否相交。

2. 链表中间

问题：找到单链表的中间元素。
解决方案： 移动一个指针的速度是另一个指针的两倍；当较快的指针到达末尾时，较慢的指针将落在中间。

3. 快乐数字

问题：如果一个数字以任何正整数开头，用其数字的平方和替换该数字最终得到 1，则该数字被视为“快乐”。如果不是，则序列将输入一个循环。检测一个数字是否是一个快乐的数字。

模式：使用快慢指针方法来检测序列是否进入循环。

def is_happy_number(n):
    def get_next(number):
        return sum(int(digit)**2 for digit in str(number))

    slow, fast = n, get_next(n)

    while fast != 1 and slow != fast:
        slow = get_next(slow)
        fast = get_next(get_next(fast))

    return fast == 1

登录后复制