Dua Penuding: Perlahan dan Pantas
Gunakan corak penuding perlahan-pantas untuk membuang pendua dalam tempat, mengalihkan sifar dan membahagikan tatasusunan di sekitar nilai pangsi.
Dua Penuding: Perlahan dan Pantas ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Penjelasan Penuding Perlahan dan Pantas
Corak penuding perlahan-pantas (juga dikenali sebagai kura-kura dan arnab) menggunakan dua penuding yang bergerak pada kelajuan berbeza melalui jujukan yang sama. Berbeza daripada penuding hujung bertentangan, kedua-duanya bermula dari awal. Penuding perlahan bergerak satu langkah pada satu masa; penuding pantas bergerak dua langkah (atau lebih). Perbezaan kelajuan mereka menghasilkan invarian yang berguna: penuding perlahan menjejaki 'awalan sah' manakala penuding pantas mengimbas ke hadapan untuk mencari syarat.
# 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]Membuang Pendua daripada Tatasusunan Tersusun
Dalam tatasusunan tersusun, pendua adalah bersebelahan. Penuding perlahan menjejaki nilai unik terakhir yang ditulis; penuding pantas mengimbas ke hadapan. Apabila penuding pantas mencapai nilai yang berbeza daripada nums[slow], gerakkan slow dan salin nilai baharu itu. Algoritma secara setempat ini berjalan dalam masa O(n) dengan ruang tambahan O(1) — soalan temu duga standard yang menguji penguasaan corak penuding baca-tulis.
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]Menggerakkan Sifar dengan Perlahan-Pantas
Gerakkan semua sifar ke hujung sambil mengekalkan susunan relatif unsur bukan sifar. Penuding perlahan menandakan kedudukan seterusnya untuk unsur bukan sifar. Penuding pantas mengimbas nilai bukan sifar. Apabila pantas menemui satu nilai, salinnya ke kedudukan perlahan dan gerakkan kedua-duanya. Selepas imbasan, isi kedudukan dari perlahan hingga ke hujung dengan sifar. Masa O(n), ruang 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]Membahagi Tatasusunan Mengelilingi Pangsi
Sublangkah pembahagian bagi isihan pantas menyusun semula unsur secara setempat supaya semua nilai < pangsi berada sebelum nilai >= pangsi. Skim Lomuto menggunakan penuding perlahan (menandakan kedudukan terakhir unsur kecil) dan penuding pantas (mengimbas ke hadapan). Apabila pantas menemui unsur kecil, tambahkan slow dan tukar kedua-dua unsur. Ini berjalan dalam masa O(n) dengan ruang tambahan 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 <= pivotMencari Tengah Senarai Terpaut
Dengan penuding perlahan-pantas pada senarai terpaut, penuding pantas bergerak melalui dua nod bagi setiap langkah manakala penuding perlahan bergerak melalui satu nod. Apabila pantas sampai ke hujung, perlahan berada di tengah. Pendekatan satu laluan O(n) ini jauh lebih kemas berbanding mengira nod dahulu, kemudian bergerak separuh jalan. Ia digunakan sebagai sublangkah dalam isihan gabung untuk senarai terpaut dan pengesanan palindrom dalam senarai terpaut.
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)Pengesanan Kitaran: Kura-kura dan Arnab Floyd
Pengesanan kitaran Floyd meletakkan penuding perlahan dan pantas di kepala senarai terpaut. Penuding perlahan bergerak melalui satu nod; penuding pantas melalui dua nod. Jika wujud kitaran, penuding pantas akhirnya akan memintas penuding perlahan dan kedua-duanya bertemu di dalam kitaran. Jika pantas mencapai nilai tiada, tiada kitaran wujud. Pertemuan itu dijamin kerana pantas mendapat satu langkah berbanding perlahan pada setiap lelaran — dalam kitaran yang panjangnya k, kedua-duanya bertemu dalam k langkah selepas perlahan memasuki kitaran.
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)) # TrueMencari Titik Masuk Kitaran
Selepas mengesan kitaran (slow == fast), tetapkan semula salah satu penuding ke kepala. Kemudian gerakkan kedua-dua penuding satu langkah pada satu masa. Kedua-duanya akan bertemu di titik masuk kitaran. Kaedah ini menggunakan sifat matematik bahawa jarak dari kepala ke titik masuk kitaran sama dengan jarak dari titik pertemuan ke titik masuk kitaran (modulo panjang kitaran). Ini ialah hasil matematik yang indah dan kerap muncul dalam soalan temu duga yang sukar.
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)Perlahan-Pantas untuk Nombor Gembira
Penuding perlahan-pantas boleh digunakan di luar senarai terpaut untuk sebarang proses yang berulang secara kitaran. 'Nombor gembira' berputar melalui jumlah kuasa dua digit — jika n tidak gembira, jujukan itu akhirnya berulang dalam gelung. Kesan gelung itu dengan perlahan (satu langkah = satu kuasa dua digit) dan pantas (dua langkah). Jika kedua-duanya bertemu pada 1, n adalah gembira; jika tidak, n terperangkap dalam kitaran yang bukan 1. Ini ialah algoritma Floyd yang diterapkan pada senarai terpaut maya yang terdiri daripada nilai.
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)Nod ke-N dari Hujung Senarai
Cari nod ke-n dari hujung senarai terpaut dalam satu laluan menggunakan dua penuding. Gerakkan penuding pantas n langkah ke hadapan. Kemudian gerakkan kedua-dua penuding bersama-sama sehingga pantas mencapai hujung — perlahan kini berada pada nod ke-n dari hujung. Untuk memadam nod ini, simpan penuding 'sebelum' satu langkah di belakang perlahan. Ini ialah masalah senarai terpaut satu laluan klasik yang mengelakkan pengiraan panjang keseluruhan terlebih dahulu.
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->5Perlahan-Pantas dalam Masalah Rentetan
Pemikiran perlahan-pantas juga boleh digunakan pada masalah tatasusunan dan rentetan. Apabila memampatkan rentetan yang dikodkan mengikut panjang larian, penuding perlahan menandakan kedudukan penulisan dan penuding pantas mengimbas hingga ke hujung setiap larian. Apabila semua aksara dalam larian sama dengan aksara perlahan, gerakkan pantas; jika tidak, rekodkan larian itu dan kemas kini perlahan. Ini mencapai O(n) dalam satu laluan dengan ruang O(1).
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']Memilih antara Perlahan-Pantas dan Hujung Bertentangan
Gunakan penuding hujung bertentangan apabila masalah melibatkan pasangan yang jumlahnya sama dengan sasaran, pemeriksaan palindrom, atau pengecilan tetingkap dari kedua-dua sisi. Gunakan penuding perlahan-pantas apabila Anda memerlukan penuding penulisan (untuk membuang atau menggerakkan unsur), ketika memproses struktur senarai terpaut (tengah, kitaran), atau ketika mengesan kitaran dalam sebarang jujukan nilai. Kedua-duanya menghapuskan gelung bersarang dan mencapai O(n) — faktor penentu ialah struktur lintasan.
# 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)) # 5Semakan Pantas
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Imbas Kembali Pelajaran
Dalam pelajaran ini Anda telah mempelajari bahawa: corak perlahan-pantas (baca-tulis) mengekalkan penuding penulisan pada kedudukan sah seterusnya sementara penuding pantas mengimbas ke hadapan — asas bagi pembuangan, penyahpenduaan dan penggerakan sifar secara setempat, kura-kura dan arnab Floyd mengesan kitaran dalam masa O(n) dan ruang O(1) dengan memanfaatkan perbezaan kelajuan antara dua penuding, dan selepas mengesan kitaran, menetapkan semula satu penuding ke kepala lalu menggerakkan kedua-duanya pada kelajuan yang sama akan mencari titik masuk kitaran berdasarkan kesamaan jarak yang boleh dibuktikan. Seterusnya kita akan meneroka API rentetan Python untuk temu duga.
Pelajari Python dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “Dua Penuding: Perlahan dan Pantas” percuma?
Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Dua Penuding: Perlahan dan Pantas”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Dua Penuding: Perlahan dan Pantas”?
Gunakan corak penuding perlahan-pantas untuk membuang pendua dalam tempat, mengalihkan sifar dan membahagikan tatasusunan di sekitar nilai pangsi. Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?
Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Dua Penuding: Perlahan dan Pantas” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Asas Tatasusunan dan Operasi Dalam Tempat
- Jumlah Awalan dan Jumlah Berjalan
- Dua Penuding: Hujung Bertentangan
- Dua Penuding: Perlahan dan Pantas