Yol Sıkıştırmalı DSU
Birleştirme ve bulma işlemlerini neredeyse sabit zamanda yapın.
Yol Sıkıştırmalı DSU, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
DSU Neyi İzler
Ayrık Kümeler Birliği, öğeleri kesişmeyen kümeler halinde gruplandırır; böylece iki şeyin zaten birlikte olup olmadığını sorabilirsiniz. 🤝
Ağaçlar Olarak Kümeler
DSU her kümeyi bir ağaç olarak saklar. Her öğe bir üst düğümü gösterir; en üst düğüm olan kök, grubun benzersiz adıdır.
Üst Düğüm Dizisi
Tüm bu bağlantıları tek bir dizide tutarsınız. Her öğeyi başlangıçta kendi üst düğümü olarak ayarlayın; bu, her öğenin başlangıçta tek başına bir kümede olduğu anlamına gelir.
parent = list(range(n))Kökü Bulma
find işlemi, bir öğe kendisini gösterene kadar üst düğüm bağlantıları boyunca yukarı çıkar. Kendini gösteren bu düğüm, kümeyi tanımlayan köktür.
while parent[x] != x:
x = parent[x]Uzun Zincirler Sorun Yaratır
Dikkat edilmezse kümeler uzun ve ince zincirler oluşturabilir. Bu durumda find düğüm düğüm ilerler ve tek bir sorgu O(n) maliyetine çıkabilir; bu da çok yavaştır.
Yol Sıkıştırma Devreye Giriyor
Yol sıkıştırma bunu düzeltir: kökü bulurken ziyaret edilen her düğümü doğrudan köke bağlarsınız ve ağacı bir sonraki kullanım için düzleştirirsiniz. ⚡
Özyinelemeli Sıkıştırma
En temiz yol özyineleme kullanmaktır. Kökü bulun, ardından geri dönmeden önce onu parent[x] içine kaydedin; böylece bağlantı kalıcı olarak kısalır.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]İki Öğe Aynı Kümede mi
İki öğenin bağlantılı olup olmadığını test etmek için köklerini karşılaştırın. find(a) ile find(b) eşitse aynı gruptadırlar; aksi halde hâlâ ayrıdırlar.
if find(a) == find(b):
print("connected")İki Kümeyi Birleştirme
union işlemi, köklerden birini diğerinin altına bağlayarak grupları birleştirir. Tek bir satır, iki ağacın tamamını tek bir kümede birleştirir.
def union(a, b):
parent[find(a)] = find(b)Neden Bu Kadar Hızlı
Yalnızca sıkıştırmayla işlemler yaklaşık O(log n) itfa edilmiş maliyetle çalışır; sıralamayla birlikte kullanıldığında sorgu başına süre sabite yaklaşır.
DSU'nun Parladığı Yerler
DSU, bağlantılılık sorularını çözer: arkadaş çevreleri, ağ bileşenleri ve Kruskal'ın kapsayan ağacı hızlı find ve union işlemlerine dayanır. 🌐
Hızlı Kontrol
Yol sıkıştırmanın gerçekte neyi değiştirdiğini düşünün.
Tekrar
Bir DSU oluşturdunuz: bir üst düğüm dizisi, kökü bulmak için find ve kümeleri birleştirmek için union. Yol sıkıştırma, yapıyı son derece hızlı tutar. Harika iş! 🎉
Sıkça Sorulan Sorular
“Yol Sıkıştırmalı DSU” dersi ücretsiz mi?
Evet — “Yol Sıkıştırmalı DSU” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Yol Sıkıştırmalı DSU” dersinde ne öğreneceğim?
Birleştirme ve bulma işlemlerini neredeyse sabit zamanda yapın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.
“Yol Sıkıştırmalı DSU” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Yol Sıkıştırmalı DSU
- Rütbeye Göre Birleştirme ve Bileşenler
- Kruskal'ın Minimum Örtücü Ağacı
- Yığınla Prim'in MST'si