Dwa wskaźniki: wolny i szybki
Zastosują Państwo wzorzec wolnego i szybkiego wskaźnika do usuwania duplikatów w miejscu, przenoszenia zer i dzielenia tablicy względem wartości osi podziału.
Dwa wskaźniki: wolny i szybki to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Wyjaśnienie wolnego i szybkiego wskaźnika
Wzorzec wolnego i szybkiego wskaźnika, nazywany również wzorcem żółwia i zająca, wykorzystuje dwa wskaźniki poruszające się z różnymi prędkościami po tej samej sekwencji. W przeciwieństwie do wskaźników poruszających się od przeciwnych końców oba zaczynają na początku. Wolny wskaźnik przesuwa się o jeden krok, a szybki o dwa (lub więcej). Różnica prędkości tworzy użyteczne niezmienniki: wolny wskaźnik śledzi „poprawny prefiks”, podczas gdy szybki skanuje kolejne elementy w poszukiwaniu określonych warunków.
# 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]Usuwanie duplikatów z posortowanej tablicy
W posortowanej tablicy duplikaty znajdują się obok siebie. Wolny wskaźnik wskazuje ostatnią zapisaną unikalną wartość, a szybki wskaźnik skanuje kolejne elementy. Gdy szybki wskaźnik napotka wartość różną od nums[slow], należy przesunąć wolny wskaźnik i skopiować nową wartość. Ten algorytm wykonywany w miejscu działa w czasie O(n) i wykorzystuje O(1) dodatkowej pamięci — jest to standardowe pytanie rekrutacyjne sprawdzające znajomość wzorca wskaźnika odczytu i zapisu.
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]Przenoszenie zer za pomocą wolnego i szybkiego wskaźnika
Należy przenieść wszystkie zera na koniec, zachowując względną kolejność elementów niezerowych. Wolny wskaźnik wskazuje następną pozycję dla elementu niezerowego. Szybki wskaźnik skanuje tablicę w poszukiwaniu wartości niezerowych. Gdy szybki wskaźnik znajdzie taką wartość, należy skopiować ją na pozycję wolnego wskaźnika i przesunąć oba wskaźniki. Po zakończeniu skanowania należy wypełnić pozycje od wolnego wskaźnika do końca zerami. Złożoność czasowa wynosi O(n), a pamięciowa 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]Partycjonowanie tablicy względem pivota
Podetap sortowania szybkiego, czyli partycjonowanie, przestawia elementy w miejscu tak, aby wszystkie wartości < pivot znajdowały się przed wartościami >= pivot. Schemat Lomuto wykorzystuje wolny wskaźnik oznaczający ostatnią pozycję małego elementu oraz szybki wskaźnik skanujący tablicę w przód. Gdy szybki wskaźnik znajdzie mały element, należy zwiększyć wartość wolnego wskaźnika i zamienić elementy miejscami. Algorytm działa w czasie O(n) i wykorzystuje O(1) dodatkowej pamięci.
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 <= pivotZnajdowanie środka listy wiązanej
W przypadku wolnego i szybkiego wskaźnika użytych na liście wiązanej szybki wskaźnik przesuwa się o dwa węzły w jednym kroku, a wolny o jeden. Gdy szybki wskaźnik dotrze do końca, wolny znajduje się w środku listy. To jednoprzebiegowe podejście o złożoności O(n) jest znacznie prostsze niż policzenie węzłów, a następnie przejście do połowy listy. Jest używane jako podetap sortowania przez scalanie list wiązanych oraz podczas wykrywania palindromów w listach wiązanych.
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)Wykrywanie cyklu: żółw i zając Floyda
Algorytm wykrywania cyklu Floyda ustawia wolny i szybki wskaźnik na początku listy wiązanej. Wolny wskaźnik przesuwa się o jeden węzeł, a szybki o dwa. Jeśli istnieje cykl, szybki wskaźnik w końcu dogoni wolny i oba spotkają się wewnątrz cyklu. Jeśli szybki wskaźnik dotrze do None, cykl nie istnieje. Spotkanie jest gwarantowane, ponieważ w każdej iteracji szybki wskaźnik zyskuje nad wolnym jeden krok — w cyklu o długości k oba wskaźniki spotkają się w ciągu k kroków od wejścia wolnego wskaźnika do cyklu.
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)) # TrueZnajdowanie punktu wejścia do cyklu
Po wykryciu cyklu (slow == fast) należy ustawić jeden ze wskaźników z powrotem na początku listy. Następnie oba wskaźniki należy przesuwać o jeden krok naraz. Spotkają się w punkcie wejścia do cyklu. Wykorzystuje to matematyczną własność, zgodnie z którą odległość od początku listy do punktu wejścia do cyklu jest równa odległości od punktu spotkania do punktu wejścia do cyklu (modulo długość cyklu). To elegancki wynik matematyczny, który często pojawia się w trudnych zadaniach rekrutacyjnych.
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)Wolny i szybki wskaźnik dla szczęśliwej liczby
Wolny i szybki wskaźnik można stosować nie tylko do list wiązanych, lecz także do dowolnego procesu, w którym mogą wystąpić cykle. „Szczęśliwa liczba” przechodzi przez sekwencję sum kwadratów cyfr — jeśli n nie jest szczęśliwe, sekwencja w końcu zaczyna się powtarzać. Pętlę należy wykryć za pomocą wolnego wskaźnika (jeden krok = jedna suma kwadratów cyfr) i szybkiego wskaźnika (dwa kroki). Jeśli oba wskaźniki spotkają się w wartości 1, n jest szczęśliwe; w przeciwnym razie utknęły w cyklu niezawierającym wartości 1. Jest to algorytm Floyda zastosowany do wirtualnej listy wiązanej wartości.
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-ty węzeł od końca listy
Należy znaleźć n-ty węzeł od końca listy wiązanej w jednym przebiegu, używając dwóch wskaźników. Najpierw należy przesunąć szybki wskaźnik o n kroków do przodu. Następnie oba wskaźniki należy przesuwać razem, aż szybki dotrze do końca — wolny będzie wtedy wskazywać n-ty węzeł od końca. Aby usunąć ten węzeł, należy zachować wskaźnik „prev” o jeden krok za wolnym wskaźnikiem. Jest to klasyczny jednoprzebiegowy problem dotyczący list wiązanych, który pozwala uniknąć wcześniejszego zliczania całkowitej długości listy.
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->5Wolny i szybki wskaźnik w zadaniach dotyczących napisów
Myślenie w kategoriach wolnego i szybkiego wskaźnika przydaje się również w zadaniach dotyczących tablic i napisów. Podczas kompresowania napisu z kodowaniem długości serii wolny wskaźnik wskazuje pozycję zapisu, a szybki skanuje do końca każdej serii. Jeśli wszystkie znaki w serii są równe znakowi wskazywanemu przez wolny wskaźnik, należy przesunąć szybki wskaźnik; w przeciwnym razie należy zapisać serię i zaktualizować wolny wskaźnik. Zapewnia to złożoność O(n) w jednym przebiegu i wykorzystuje O(1) pamięci.
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']Wybór między wskaźnikami wolnym i szybkim a wskaźnikami od przeciwnych końców
Wskaźników poruszających się od przeciwnych końców należy używać, gdy problem dotyczy par o sumie równej wartości docelowej, sprawdzania palindromu lub zwężania okna z obu stron. Wskaźników wolnego i szybkiego należy używać, gdy potrzebny jest wskaźnik zapisu (do usuwania lub przenoszenia elementów), podczas przetwarzania struktury listy wiązanej (środek, cykl) albo do wykrywania cykli w dowolnej sekwencji wartości. Oba wzorce eliminują zagnieżdżone pętle i osiągają złożoność O(n) — decydujące znaczenie ma struktura przejścia.
# 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)) # 5Szybki sprawdzian
Sprawdź swoją wiedzę na temat zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji poznano: wzorzec wolnego i szybkiego wskaźnika (odczytu i zapisu) utrzymuje wskaźnik zapisu na następnej poprawnej pozycji, podczas gdy szybki wskaźnik skanuje kolejne elementy — jest podstawą usuwania elementów, usuwania duplikatów i przenoszenia zer w miejscu, algorytm żółwia i zająca Floyda wykrywa cykle w czasie O(n) i przy użyciu O(1) pamięci, wykorzystując różnicę prędkości dwóch wskaźników oraz po wykryciu cyklu ustawienie jednego wskaźnika na początku listy i przesuwanie obu z taką samą prędkością pozwala znaleźć punkt wejścia do cyklu dzięki możliwej do udowodnienia równości odległości. Następnie omówione zostanie API napisów w Pythonie przydatne podczas rozmów rekrutacyjnych.
Często zadawane pytania
Czy lekcja „Dwa wskaźniki: wolny i szybki” jest bezpłatna?
Tak — pełny tekst „Dwa wskaźniki: wolny i szybki” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Dwa wskaźniki: wolny i szybki”?
Zastosują Państwo wzorzec wolnego i szybkiego wskaźnika do usuwania duplikatów w miejscu, przenoszenia zer i dzielenia tablicy względem wartości osi podziału. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Dwa wskaźniki: wolny i szybki”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Podstawy tablic i operacje w miejscu
- Sumy prefiksowe i sumy narastające
- Dwa wskaźniki: przeciwległe końce
- Dwa wskaźniki: wolny i szybki