ตัวชี้สองตัว: ช้าและเร็ว

อธิบายตัวชี้ช้าและเร็ว

# Slow pointer marks the write position;
# Fast pointer scans for next non-duplicate.

def remove_duplicates(nums):
    if not nums: return 0
    slow = 0  # next position to write a unique value
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1  # new length

nums = [1, 1, 2, 3, 3, 3, 4]
k = remove_duplicates(nums)
print(nums[:k])  # [1, 2, 3, 4]

ลบค่าซ้ำจากอาร์เรย์ที่เรียงลำดับ

def remove_duplicates_v2(nums):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

# Allow at most 2 occurrences
def remove_duplicates_k2(nums):
    slow = 0
    for fast in range(len(nums)):
        if slow < 2 or nums[fast] != nums[slow - 2]:
            nums[slow] = nums[fast]
            slow += 1
    return slow

print(remove_duplicates_k2([1,1,1,2,2,3]))
# Result: 5, nums[:5] = [1,1,2,2,3]

ย้ายเลขศูนย์ด้วยตัวชี้ช้า-เร็ว

def move_zeroes(nums):
    slow = 0  # next position for a non-zero
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow] = nums[fast]
            slow += 1
    # Fill rest with zeroes
    while slow < len(nums):
        nums[slow] = 0
        slow += 1

nums = [0, 1, 0, 3, 12]
move_zeroes(nums)
print(nums)  # [1, 3, 12, 0, 0]

แบ่งอาร์เรย์รอบจุดหมุน

def lomuto_partition(nums, low, high):
    pivot = nums[high]
    slow = low - 1  # last position of small element
    for fast in range(low, high):
        if nums[fast] <= pivot:
            slow += 1
            nums[slow], nums[fast] = nums[fast], nums[slow]
    # Place pivot in final position
    nums[slow+1], nums[high] = nums[high], nums[slow+1]
    return slow + 1  # pivot's final index

arr = [3, 1, 4, 1, 5, 9, 2, 6]
p = lomuto_partition(arr, 0, len(arr)-1)
print(arr)   # elements before p are <= pivot

ค้นหาโหนดกลางของรายการเชื่อมโยง

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # slow is at middle

# Build 1->2->3->4->5
h = Node(1, Node(2, Node(3, Node(4, Node(5)))))
mid = find_middle(h)
print(mid.val)  # 3  (middle of 5 nodes)

การตรวจจับวัฏจักร: เต่ากับกระต่ายของฟลอยด์

class ListNode:
    def __init__(self, val=0, nxt=None):
        self.val = val
        self.next = nxt

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:  # identity check (same object)
            return True
    return False

# 1->2->3->4->2 (cycle at node 2)
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n1.next=n2; n2.next=n3; n3.next=n4; n4.next=n2
print(has_cycle(n1))  # True

ค้นหาจุดเริ่มต้นของวัฏจักร

def detect_cycle(head):
    slow = fast = head
    # Phase 1: detect
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None  # no cycle
    # Phase 2: find entry
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    return slow  # cycle entry node

# Using same cycled list as previous scene
print(detect_cycle(n1).val)  # 2  (cycle entry)

ตัวชี้ช้า-เร็วสำหรับเลขมีความสุข

def is_happy(n):
    def next_val(x):
        total = 0
        while x:
            x, d = divmod(x, 10)
            total += d * d
        return total

    slow = n
    fast = next_val(n)
    while fast != 1 and slow != fast:
        slow = next_val(slow)
        fast = next_val(next_val(fast))
    return fast == 1

print(is_happy(19))   # True  (1->9->...->1)
print(is_happy(2))    # False (enters a cycle)

โหนดลำดับที่ n จากท้ายรายการ

def remove_nth_from_end(head, n):
    dummy = ListNode(0)
    dummy.next = head
    fast = slow = dummy
    # Advance fast n+1 steps
    for _ in range(n + 1):
        fast = fast.next
    # Advance together
    while fast:
        slow = slow.next
        fast = fast.next
    # slow.next is the nth from end
    slow.next = slow.next.next
    return dummy.next

# Build 1->2->3->4->5, remove 2nd from end
h2 = ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))
result = remove_nth_from_end(h2, 2)
# Should give 1->2->3->5

ตัวชี้ช้า-เร็วในโจทย์สตริง

def compress(chars):
    slow = fast = 0
    while fast < len(chars):
        char = chars[fast]
        count = 0
        # Count the run
        while fast < len(chars) and chars[fast] == char:
            fast += 1
            count += 1
        chars[slow] = char
        slow += 1
        if count > 1:
            for c in str(count):
                chars[slow] = c
                slow += 1
    return slow

chars = list('aabcccccaa')
print(compress(chars))  # 6
print(chars[:6])        # ['a','2','b','c','5','a']... wait
# Actually: ['a','2','b','c','5','a','2']

การเลือกใช้ตัวชี้ช้า-เร็วหรือตัวชี้จากปลายตรงข้าม

# Pattern matcher:
# 1. Sorted array, target sum -> OPPOSITE ENDS
# 2. Remove/filter elements in-place -> SLOW-FAST (read-write)
# 3. Linked list middle/cycle -> SLOW-FAST (1x vs 2x speed)
# 4. Detect cycle in value sequence -> SLOW-FAST (Floyd)

# Example: given sorted array, remove val in-place
def remove_sorted(nums, val):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    return slow

nums = [0,1,2,2,3,0,4,2]
print(remove_sorted(nums, 2))  # 5

ตรวจสอบความเข้าใจ

สรุปบทเรียน