PricingLoginStart free
Forberedelse til kodeintervjuer · leksjon

To pekere: langsom og rask

Bruk mønsteret med langsom og rask peker til å fjerne duplikater in-place, flytte nuller og dele arrayer rundt en pivotverdi.

Leksjon 4 av 413 trinn

To pekere: langsom og rask er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Slow-fast-pekere forklart

Slow-fast-peker-mønsteret (også kalt skilpadde-og-hare) bruker to pekere som beveger seg med ulik hastighet gjennom samme sekvens. I motsetning til pekere fra motsatte ender starter begge i begynnelsen. Slow-pekeren flyttes ett steg om gangen, mens fast-pekeren flyttes to (eller flere). Forskjellen i hastighet skaper nyttige invarianter: slow-pekeren følger et «gyldig prefiks», mens fast-pekeren skanner fremover etter betingelser.

# 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]

Fjern duplikater fra sortert array

I et sortert array ligger duplikater ved siden av hverandre. Slow-pekeren holder oversikt over den siste unike verdien som er skrevet, mens fast-pekeren skanner fremover. Når fast-pekeren når en verdi som er forskjellig fra nums[slow], flytter De slow fremover og kopierer den nye verdien. Denne in-place-algoritmen bruker O(n) tid og O(1) ekstra plass – et vanlig intervjuspørsmål som tester hvor godt De behersker lese-skrive-peker-mønsteret.

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]

Flytt nuller med slow-fast-pekere

Flytt alle nuller til slutten samtidig som den innbyrdes rekkefølgen til elementene som ikke er null, bevares. Slow-pekeren markerer neste posisjon for et element som ikke er null. Fast-pekeren skanner etter verdier som ikke er null. Når fast finner en slik verdi, kopierer De den til slow-posisjonen og flytter begge fremover. Etter gjennomløpet fyller De posisjonene fra slow til slutten med nuller. O(n) tid og O(1) plass.

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]

Partisjoner et array rundt en pivot

Partisjoneringssteget i quicksort omorganiserer elementene på stedet slik at alle verdier < pivot kommer før verdier >= pivot. Lomuto-skjemaet bruker en slow-peker (som markerer den siste posisjonen for et lite element) og en fast-peker (som skanner fremover). Når fast finner et lite element, øker De slow og bytter om elementene. Dette bruker O(n) tid og O(1) ekstra plass.

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

Finn midten av en lenket liste

Med slow-fast-pekere i en lenket liste flytter fast-pekeren seg to noder per steg, mens slow-pekeren flytter seg én. Når fast når slutten, står slow i midten. Denne ett-gjennomløpsmetoden med O(n) er langt ryddigere enn først å telle nodene og deretter gå halvveis gjennom listen. Den brukes som et delsteg i mergesort for lenkede lister og ved deteksjon av palindromer i lenkede lister.

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)

Syklusdeteksjon: Floyds skilpadde og hare

Floyds syklusdeteksjon plasserer slow- og fast-pekeren ved hodet av en lenket liste. Slow flyttes én node, mens fast flyttes to. Hvis det finnes en syklus, vil fast-pekeren til slutt ta igjen slow-pekeren, og de møtes inne i syklusen. Hvis fast når None, finnes det ingen syklus. Møtet er garantert fordi fast tar inn ett steg på slow i hver iterasjon – i en syklus med lengde k møtes de innen k steg etter at slow går inn i syklusen.

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

Finn syklusens inngangspunkt

Etter at en syklus er oppdaget (slow == fast), tilbakestiller De én peker til head. Flytt nå begge pekerne ett steg om gangen. De møtes ved syklusens inngangspunkt. Dette bygger på den matematiske egenskapen at avstanden fra head til syklusens inngang er lik avstanden fra møtestedet til syklusens inngang (modulo syklusens lengde). Dette er et elegant matematisk resultat som ofte dukker opp i krevende intervjuproblemer.

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)

Slow-fast for lykketall

Slow-fast-pekere kan brukes på mer enn lenkede lister, nemlig i alle prosesser som går i syklus. Et «lykketall» går i syklus gjennom summer av sifferkvadrater – hvis n ikke er et lykketall, vil sekvensen til slutt gå i løkke. Oppdag løkken med slow (ett steg = ett sifferkvadrat) og fast (to steg). Hvis de møtes ved 1, er n et lykketall; ellers sitter tallet fast i en syklus som ikke inneholder 1. Dette er Floyds algoritme brukt på en virtuell lenket liste med verdier.

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)

Den n-te noden fra slutten av en liste

Finn den n-te noden fra slutten av en lenket liste i ett gjennomløp ved hjelp av to pekere. Flytt fast-pekeren n steg fremover. Flytt deretter begge pekerne sammen til fast når slutten – slow står nå ved den n-te noden fra slutten. For å slette denne noden beholder De en «prev»-peker ett steg bak slow. Dette er et klassisk problem om lenkede lister i ett gjennomløp, som unngår å telle den totale lengden først.

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

Slow-fast i strengproblemer

Slow-fast-tenkning kan også brukes i array- og strengproblemer. Ved komprimering av en run-length-kodet streng markerer slow-pekeren skriveposisjonen, mens fast-pekeren skanner til slutten av hver sekvens. Når alle tegnene i sekvensen er lik tegnet til slow, flytter De fast fremover; ellers registrerer De sekvensen og oppdaterer slow. Dette oppnår O(n) i ett gjennomløp med O(1) plass.

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']

Velge mellom slow-fast-pekere og pekere fra motsatte ender

Bruk pekere fra motsatte ender når problemet gjelder par som summerer til et mål, palindromkontroll eller å snevre inn et vindu fra begge sider. Bruk slow-fast-pekere når De trenger en skrivepeker (for å fjerne eller flytte elementer), når De behandler strukturen til en lenket liste (midte, syklus), eller når De oppdager sykluser i en hvilken som helst verdisekvens. Begge eliminerer nøstede løkker og oppnår O(n) – den avgjørende faktoren er traverseringens struktur.

# 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

Kunnskapssjekk

Test forståelsen Deres av konseptene fra Data Structures & Algorithms — Coding Interview Prep i denne leksjonen.

Besvar den i den interaktive leksjonen

Oppsummering av leksjonen

I denne leksjonen lærte De: slow-fast-mønsteret (lese-skrive-mønsteret) holder en skrivepeker på neste gyldige posisjon mens en fast peker skanner fremover – grunnlaget for å fjerne, deduplisere og flytte nuller på stedet, Floyds skilpadde-og-hare-algoritme oppdager sykluser på O(n)-tid og med O(1) plass ved å utnytte hastighetsforskjellen mellom to pekere, og etter syklusdeteksjon finner man syklusens inngang ved å tilbakestille én peker til head og flytte begge med samme hastighet, takket være en bevisbar likhet mellom avstander. Deretter utforsker vi Python-API-et for strenger i intervjuer.

Gratis å komme i gang

Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs
90
Leksjoner
360
Start læringen gratisSe hele kurset

Ofte stilte spørsmål

Er leksjonen «To pekere: langsom og rask» gratis?

Ja – hele teksten i «To pekere: langsom og rask» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Hva lærer jeg i «To pekere: langsom og rask»?

Bruk mønsteret med langsom og rask peker til å fjerne duplikater in-place, flytte nuller og dele arrayer rundt en pivotverdi. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?

Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.

Hvor lang tid tar leksjonen «To pekere: langsom og rask»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?

Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

  1. Grunnleggende om arrays og in-place-operasjoner
  2. Prefikssummer og løpende totaler
  3. To pekere: motsatte ender
  4. To pekere: langsom og rask
← Tilbake til Forberedelse til kodeintervjuer