Kaksi osoitinta: hidas ja nopea
Soveltakaa hitaan ja nopean osoittimen mallia duplikaattien poistamiseen paikallaan, nollien siirtämiseen ja taulukoiden jakamiseen pivot-arvon ympärille.
Kaksi osoitinta: hidas ja nopea on ilmainen DSA Interview Prep-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea tästä oppimispolusta kokonaan mitkä tahansa 3 oppituntia ilmaiseksi — sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä käytännön harjoittelun sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. Oppitunti kuuluu DSA Interview Prep-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. DSA Interview Prep-kurssilla on yhteensä 4 oppituntia.
Hitaat ja nopeat osoittimet selitettynä
Hitaiden ja nopeiden osoittimien malli (jota kutsutaan myös kilpikonna ja jänis -malliksi) käyttää kahta osoitinta, jotka liikkuvat eri nopeuksilla samassa sekvenssissä. Toisin kuin vastakkaisista päistä etenevät osoittimet, molemmat alkavat alusta. Hidas osoitin etenee yhden askeleen kerrallaan, kun taas nopea osoitin etenee kaksi (tai useampia). Nopeusero luo hyödyllisiä invariantteja: hidas osoitin seuraa "kelvollista etuliitettä", kun taas nopea osoitin etsii edempää ehtoja.
# 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]Duplikaattien poistaminen järjestetystä taulukosta
Järjestetyssä taulukossa duplikaatit ovat vierekkäin. Hidas osoitin seuraa viimeksi kirjoitettua yksilöllistä arvoa, ja nopea osoitin käy eteenpäin. Aina kun nopea osoitin saavuttaa arvon, joka poikkeaa arvosta nums[slow], siirtäkää hidasta osoitinta ja kopioikaa uusi arvo. Tämä paikallaan toimiva algoritmi käyttää aikaa O(n) ja ylimääräistä tilaa O(1) — kyseessä on tavallinen haastattelukysymys, jolla testataan luku-kirjoitusosoittimen mallin hallintaa.
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]Nollien siirtäminen hitaiden ja nopeiden osoittimien avulla
Siirtäkää kaikki nollat loppuun säilyttäen samalla nollasta poikkeavien alkioiden keskinäinen järjestys. Hidas osoitin merkitsee seuraavaa paikkaa, johon nollasta poikkeava alkio sijoitetaan. Nopea osoitin etsii nollasta poikkeavia arvoja. Kun nopea osoitin löytää sellaisen, kopioikaa se hitaan osoittimen kohdalle ja siirtäkää molempia osoittimia. Täytätte skannauksen jälkeen hitaan osoittimen kohdalta taulukon loppuun ulottuvat paikat nollilla. Aikavaativuus on O(n) ja tilavaativuus O(1).
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]Taulukon jakaminen pivotin ympärille
Pikalajittelun jakamisvaihe järjestää alkiot paikallaan niin, että kaikki arvot < pivot ovat ennen arvoja >= pivot. Lomuto-mallissa hidas osoitin merkitsee pienen alkion viimeistä sijaintia ja nopea osoitin käy taulukkoa eteenpäin. Kun nopea osoitin löytää pienen alkion, kasvattakaa hidasta osoitinta ja vaihtakaa alkiot keskenään. Tämä toimii ajassa O(n) ja käyttää ylimääräistä tilaa O(1).
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 <= pivotLinkitetyn listan keskikohdan etsiminen
Kun käytätte hitaiden ja nopeiden osoittimien tekniikkaa linkitetyssä listassa, nopea osoitin siirtyy kaksi solmua joka askeleella ja hidas osoitin yhden. Kun nopea osoitin saavuttaa lopun, hidas osoitin on keskikohdassa. Tämä yhden läpikäynnin O(n)-menetelmä on paljon selkeämpi kuin solmujen laskeminen ja sen jälkeen puoliväliin kulkeminen. Sitä käytetään linkitettyjen listojen lomituslajittelun alavaiheena sekä palindromin tunnistamiseen linkitetystä listasta.
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)Syklien tunnistus: Floydin kilpikonna ja jänis
Floydin syklintunnistusalgoritmi sijoittaa hitaat ja nopeat osoittimet linkitetyn listan alkuun. Hidas osoitin siirtyy yhden solmun ja nopea kaksi. Jos sykli on olemassa, nopea osoitin saavuttaa lopulta hitaan osoittimen ja ne kohtaavat syklin sisällä. Jos nopea osoitin saavuttaa arvon None, sykliä ei ole. Kohtaaminen on varmaa, koska nopea osoitin saavuttaa hitaan yhdellä askeleella jokaisella iteraatiolla — k:n pituisessa syklissä ne kohtaavat viimeistään k askeleen kuluttua siitä, kun hidas osoitin siirtyy sykliin.
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)) # TrueSyklin alkupisteen etsiminen
Kun sykli on havaittu (slow == fast), palauttakaa toinen osoitin alkuun. Etenkää nyt molemmilla osoittimilla yksi askel kerrallaan. Ne kohtaavat syklin alkupisteessä. Tämä perustuu matemaattiseen ominaisuuteen, jonka mukaan etäisyys alusta syklin alkupisteeseen on sama kuin etäisyys kohtaamispisteestä syklin alkupisteeseen (syklin pituuden modulo). Tämä on hieno matemaattinen tulos, joka esiintyy usein vaativissa haastatteluongelmissa.
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)Hitaat ja nopeat osoittimet onnelliselle luvulle
Hitaiden ja nopeiden osoittimien tekniikkaa voi käyttää linkitettyjen listojen lisäksi kaikissa prosesseissa, joissa esiintyy sykli. "Onnellinen luku" kiertää numeroiden neliöiden summien kautta — jos n ei ole onnellinen, jono päätyy lopulta silmukkaan. Tunnistakaa silmukka hitaalla osoittimella (yksi askel = yhden numeron neliö) ja nopealla osoittimella (kaksi askelta). Jos ne kohtaavat arvossa 1, n on onnellinen; muussa tapauksessa se jää kiinni muuhun kuin 1:een päätyvään sykliin. Tämä on Floydin algoritmi, jota sovelletaan arvoista muodostuvaan virtuaaliseen linkitettyyn listaan.
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)Listan n:nnen alkion etsiminen lopusta
Etsikää linkitetyn listan n:s alkio lopusta yhden läpikäynnin aikana käyttämällä kahta osoitinta. Siirtäkää nopea osoitin n askelta edelle. Siirtäkää sitten molempia osoittimia yhdessä, kunnes nopea osoitin saavuttaa lopun — hidas osoitin on nyt lopusta n:s alkio. Jos haluatte poistaa tämän alkion, pitäkää mukana askelen hitaan osoittimen jäljessä olevaa 'prev'-osoitinta. Tämä on klassinen yhden läpikäynnin linkitetyn listan ongelma, jossa kokonaispituutta ei tarvitse laskea ensin.
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->5Hitaat ja nopeat osoittimet merkkijono-ongelmissa
Hitaiden ja nopeiden osoittimien ajattelutapaa voi soveltaa myös taulukko- ja merkkijono-ongelmiin. Kun tiivistätte ajopituuskoodatun merkkijonon, hidas osoitin merkitsee kirjoituskohtaa ja nopea osoitin käy kunkin jakson loppuun. Kun kaikki jakson merkit ovat samoja kuin hitaan osoittimen merkki, siirtäkää nopeaa osoitinta; muussa tapauksessa tallentakaa jakso ja päivittäkää hidasta osoitinta. Näin saavutetaan O(n) yhden läpikäynnin aikana ja O(1):n tilankäytöllä.
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']Hitaiden ja nopeiden osoittimien ja vastakkaisista päistä etenevien osoittimien valinta
Käyttäkää vastakkaisista päistä eteneviä osoittimia, kun ongelmassa käsitellään tavoitesummaan yltäviä pareja, palindromin tarkistamista tai ikkunan supistamista molemmista päistä. Käyttäkää hitaiden ja nopeiden osoittimien tekniikkaa, kun tarvitsette kirjoitusosoitinta (alkioiden poistamiseen tai siirtämiseen), kun käsittelette linkitetyn listan rakennetta (keskikohta, sykli) tai kun tunnistatte syklejä missä tahansa arvojaksossa. Molemmat tekniikat poistavat sisäkkäiset silmukat ja saavuttavat ajan O(n) — ratkaiseva tekijä on läpikäynnin rakenne.
# 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)) # 5Pikatarkistus
Testatkaa ymmärrystänne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteistä.
Oppitunnin yhteenveto
Tässä oppitunnissa opitte, että hitaiden ja nopeiden osoittimien eli luku–kirjoitusmalli pitää kirjoitusosoittimen seuraavassa kelvollisessa sijainnissa samalla kun nopea osoitin käy eteenpäin — tämä muodostaa paikallaan tapahtuvan poistamisen, duplikaattien poistamisen ja nollien siirtämisen perustan, Floydin kilpikonna ja jänis -menetelmä tunnistaa syklit ajassa O(n) ja tilassa O(1) hyödyntämällä kahden osoittimen nopeuseroa ja syklin havaitsemisen jälkeen toisen osoittimen palauttaminen alkuun ja molempien eteneminen samalla nopeudella löytää syklin alkupisteen todistettavan etäisyyksien yhtäsuuruuden ansiosta. Seuraavaksi tutustumme Pythonin merkkijono-APIin haastatteluja varten.
Opi Python tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”Kaksi osoitinta: hidas ja nopea” ilmainen?
Kyllä — voit lukea täällä verkossa kokonaan ilmaiseksi mitkä tahansa DSA Interview Prep-oppimispolun 3 oppituntia, myös oppitunnin “Kaksi osoitinta: hidas ja nopea”. Sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä interaktiiviset harjoitukset sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. DSA Interview Prep-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Kaksi osoitinta: hidas ja nopea”?
Soveltakaa hitaan ja nopean osoittimen mallia duplikaattien poistamiseen paikallaan, nollien siirtämiseen ja taulukoiden jakamiseen pivot-arvon ympärille. Harjoittelet DSA Interview Prep-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni DSA Interview Prep-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin DSA Interview Prep-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.
Kuinka kauan ”Kaksi osoitinta: hidas ja nopea”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä DSA Interview Prep-oppitunnilla?
Kyllä. Jokainen DSA Interview Prep-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Taulukoiden perusteet ja paikallaan toimivat operaatiot
- Prefiksisummat ja juoksevat summat
- Kaksi osoitinta: vastakkaiset päät
- Kaksi osoitinta: hidas ja nopea