Sliding Window Yöntemi ile Verimli Pattern Tespiti
Sliding Window Yöntemi ile Verimli Sliding Window Yöntemi ile Verimli kapsamında, Görev Başlıyor ("Neden") Hiç iç içe döngüler arasında sıkışıp kaldığınızı, görüşmeci kibarca başını sallarken çalışma zamanı balonunuzu O(n)'den O(n^2)'ye izlediğinizi hissettiniz mi? Orada bulundum. Sorunun…
Sliding Window Yöntemi ile Verimli
Sliding Window Yöntemi ile Verimli kapsamında, Görev Başlıyor (“Neden”) Hiç iç içe döngüler arasında sıkışıp kaldığınızı, görüşmeci kibarca başını sallarken çalışma zamanı balonunuzu O(n)’den O(n^2)’ye izlediğinizi hissettiniz mi? Orada bulundum. Sorunun “en fazla K farklı karakter içeren en uzun alt dizeyi bulmak” olduğu bir beyaz tahta röportajını hatırlıyorum.
Sliding Window Yöntemi ile Verimli kapsamında, İlk denemem mümkün olan her pencereyi kontrol eden bir double-for döngüsüydü ve saniyelerin akıp gittiğini görebiliyordum. Beynim çığlık attı: Daha önce baktığım her şeyi tekrar kontrol etmeden ipin üzerinden geçmenin daha akıllıca bir yolu olmalı. O an, kayan pencere tekniği arayışımı başlattı; acımasız bir O(n^2) çabasını temiz bir O(n) zaferine dönüştüren basit bir fikir.
Sliding Window Yöntemi ile Verimli kapsamında, Vahiy (İçgörü) Kayar pencere sihirli değildir; bu sadece işi yeniden kullanmanın disiplinli bir yoludur. Bir alt dizeyi sınırlayan sol ve sağ bir işaretçi çiftiniz olduğunu hayal edin. Sağa doğru genişledikçe bazı durumları güncellersiniz (frekans haritası gibi).
Tasarım ve teknik ayrıntılar
Sliding Window Yöntemi ile Verimli kapsamında, Pencere kısıtlamayı ihlal ettiğinde (çok fazla farklı karakter, toplam çok büyük vb.), sola doğru hareket ederek pencereyi küçültür ve durumu yeniden güncellersiniz. Her dizin en fazla iki kez (biri sağdan, biri soldan) ziyaret edildiğinden, toplam iş doğrusal kalır. Bu neden O(n) veriyor?
Sliding Window Yöntemi ile Verimli kapsamında, Her öğe, sağ ileri doğru hareket ettiğinde pencereye tam olarak bir kez girer ve sol ileri doğru hareket ettiğinde tam olarak bir kez ayrılır. Hiçbir öğe sabit sayıdan fazla işlenmez kez olduğundan toplam işlemler n ile orantılıdır. Buradaki içgörü, taramayı hiçbir zaman sıfırdan yeniden başlatmamıza gerek olmadığıdır; Halihazırda topladığımız yararlı bilgileri saklıyoruz ve bunları aşamalı olarak ayarlıyoruz.
Sliding Window Yöntemi ile Verimli kapsamında, Gücü Kullanmak (Kod ve Örnekler) Problem 1: En Fazla K Farklı Karaktere Sahip En Uzun Alt Dizi Kaba kuvvet (tuzak) def long_substring_brute(s, k): n = uzunluk(lar) en iyi = 0 (n) aralığındaki i için: frekans = {} farklı = 0 (i, n) aralığındaki j için: ch = s[j] eğer kanal frekansta değilse: frekans[kanal] = 0 farklı += 1 frekans[kanal] += 1 eğer farklı > k ise: mola en iyi = maksimum(en iyi, j – i + 1) return best Bu çift döngü her başlangıç indeksi i’yi kontrol eder ve kısıtlama bozuluncaya kadar j’yi genişletir.
Bugünden bakınca ne kadar güvenilir?
En kötü durumda O(n^2) olur.
Kayan pencere zaferi def long_substring_sw(s, k): sol = 0 frekans = {} farklı = 0 sağ için en iyi = 0, numaralandırma(lar)da ch: # pencereyi genişlet eğer ch frek veya frek[ch] == 0’da değilse: farklı += 1 frekans[kanal] = 1 başka: freq[ch] += 1 # geçersizken daralt farklı > k ise: left_ch = s[sol] frekans[sol_kanal] -= 1 eğer frekans[sol_kanal] == 0 ise: farklı -= 1 sol += 1 # pencere [sol, sağ] geçerlidir best = max(best, right – left + 1) return best Her karakterin nasıl bir kez eklendiğine (sağa hareket) ve en fazla bir kez nasıl kaldırıldığına (sola hareket) dikkat edin.
İçteki while döngüsü birden çok kez çalışabilir, ancak tüm çalışma boyunca soldaki toplam artışlar n ile sınırlanır. Dolayısıyla frekans haritası için O(n) zaman, O(k) uzay.
Okuyucu için pratik anlamı
Sorun 2: Min imum Boyut Alt Dizi Toplamı ≥ hedef Kaba kuvvet def min_subarray_len_brute(sayılar, hedef): n = uzunluk(sayılar) en iyi = float(‘inf’) (n) aralığındaki i için: toplam = 0 (i, n) aralığındaki j için: toplam += sayılar[j] toplam >= hedef ise: en iyi = min(en iyi, j – i + 1) break # bunun için daha fazla uzatmaya gerek yok i if best == float(‘inf’) else best Again O(n^2) ise 0 değerini döndürün.
Kayan pencere düzeltmesi def min_subarray_len_sw(sayılar, hedef): sol = 0 geçerli_toplam = 0 best = sağ için float(‘inf’), numaralandırmada val(nums): current_sum += val while current_sum >= hedef: en iyi = min(en iyi, sağ – sol + 1) geçerli_toplam -= sayılar[sol] sol += 1 return 0 if best == float(‘inf’) else best Aynı mantık: her öğe toplamı bir kez girer (sağ) ve bir kez çıkar (sol).
Doğrusal zaman, sabit ekstra alan. Kaçınılması Gereken Yaygın Tuzaklar Sola hareket ederken durumu güncellemeyi unutmak (örneğin, frekansı veya toplamı azaltmamak) → pencere eski hale gelir. while içinde pencereyi yeniden tarayan yuvalanmış bir döngü kullanmak → amacı boşa çıkarır. En iyi güncellemeyi yanlış yerleştirme: yanıtı küçültmeden önce değil, yalnızca pencere geçerli olduktan sonra kaydedin.
Bu Yeni Güç Neden Önemlidir Kayan pencere modelini bir kez içselleştirdiğinizde, bir dizi görüşme problemi “zaman baskısı altında imkansız”dan “basit”e doğru çöker. Aynı iskeletle maksimum ortalama alt dizi, en uzun tekrarlanan karakter değişimi, meyve sepetleri ve daha pek çok şeyin üstesinden gelebilirsiniz. Konf.
kimlik artışı gerçektir: “bunu optimize et” takibinden korkmayı bırakırsınız ve temiz, doğrusal zamanlı çözümleri sergileme fırsatını görmeye başlarsınız. Bunu sonunda The Legend of Zelda: Breath of the Wild’da Usta Kılıcı elde etmek gibi düşünün; tahta bir sopayı sallıyordunuz ve şimdi her engeli delip geçen bir bıçağınız var. Teknik, yeni silahınızdır ve ne kadar çok pratik yaparsanız, o kadar doğal hissettirir.
Sıra Sizde Daha önce gördüğünüz bir problemi seçin (belki de “en fazla iki farklı karakter içeren en uzun alt dize” veya “minimum pencere alt dizisi”) ve kayan pencereyle yeniden yazmayı deneyin. Kodun nasıl küçüldüğüne, çalışma süresinin nasıl düştüğüne ve gülümsemenin nasıl büyüdüğüne dikkat edin. Çözümünüzü yorumlarda paylaşın veya #SlidingWindowWin etiketiyle tweet atın. Mutlu kodlama!
Şimdi kelimeleri kabaca sayın. Yaklaşık olarak hesaplayalım. Hızlı bir şekilde manuel olarak sayacağım. Başlık satırı: “Sürgülü Pencere: Kalıpları Tespit Etmenin Neo Yolu” (7 kelime?) Ancak toplamda 700-1000 kelimeye ihtiyacımız var. Her bölümü sayalım. Metni kopyalayacağım ve zihinsel kullanarak kabaca sayacağım.
Kaba bir sayım yazacağım: Kayan Pencere: Kalıpları Tespit Etmenin Neo Yolu Görev Başlıyor (“Neden”) Hiç iç içe döngüler arasında sıkışıp kaldığınızı, görüşmeci kibarca başını sallarken çalışma zamanı balonunuzu O(n)’den O(n^2)’ye izlediğinizi hissettiniz mi? Orada bulundum. Sorunun “en fazla K farklı karaktere sahip en uzun alt dizgeyi bulmak” olduğu bir beyaz tahta röportajını hatırlıyorum. rs”.
İlk denemem mümkün olan her pencereyi kontrol eden bir double-for döngüsüydü ve saniyelerin akıp gittiğini görebiliyordum. Beynim çığlık attı: daha önce baktığım her şeyi yeniden kontrol etmeden ipte kaymanın daha akıllı bir yolu olmalı. O an kayan pencere tekniği arayışımı başlattı; acımasız bir O(n^2) zorbalığını temiz bir O(n) zaferine dönüştüren basit bir fikir. Kelime sayısı yaklaşık: Hadi sayalım.
“Hiç(1)3 kendinizi4 sıkışıp kaldığınızı,6’dan 7’ye kadar iç içe geçmiş8 döngüler,9 izlediğiniz1011 çalışma sürenizi12 balon13’ten 14 O(n)15’den 16 O(n^2)17’ye kadar18 görüşmeci20 kibarca başını salladığını21 hissettiğinizi mi hissettiniz?22 Ben2324 oraya gittim.25 I26 hatırlıyorum27 a28 beyaz tahta29 röportaj30 burada3132 problem33 34 “35’i bul36 en uzun37 alt dize38 ile 39 at40 most41 K42 farklı43 karakter”.44 İlk46 denemem4748 a49 double-for50 döngüsü51 bu52 kontrol edildi53 her54 mümkün55 pencere,56 ve57 I58 görebiliyor6061 saniyeyi62 tıklıyor63 uzakta.64 My65 beynim66 çığlık attı:67 orada68 var69 ila70 be71 a72 daha akıllı73 yol74 ila75 slayt76 ila77 the78 string79 olmadan80 yeniden kontrol81 her şey82 I83 zaten84 baktım85 at.86 O87 an88 başladı89 kapalı90 my91 arayışı92 için93 the94 kayma95 pencere96 tekniği—a97 basit98 fikir99 o100 dönüş101 a102 acımasız103 O(n^2)104 slog105 into106 a107 temiz108 O(n)109 zafer110.
Yani ~110 kelime. Vahiy (İçgörü) Kayar pencere sihirli değildir; bu sadece işi yeniden kullanmanın disiplinli bir yolu. Bir alt dizeyi sınırlayan sol ve sağ bir işaretçi çiftiniz olduğunu hayal edin. Sağa doğru genişledikçe bazı durumları güncellersiniz (frekans haritası gibi).
Pencere kısıtlamayı ihlal ettiğinde (çok fazla farklı karakter, toplam çok büyük vb.), sola doğru hareket ederek pencereyi küçültür ve durumu yeniden güncellersiniz. Her dizin en fazla iki kez (biri sağdan, biri soldan) ziyaret edildiğinden, toplam iş doğrusal kalır. Bu neden O(n) veriyor?
Her öğe, sağ ileri doğru hareket ettiğinde pencereye tam olarak bir kez girer ve sol ileri doğru hareket ettiğinde tam olarak bir kez ayrılır. Hiçbir öğe sabit bir sayıdan daha fazla işlenmez, dolayısıyla toplam işlemler n ile orantılıdır. Buradaki içgörü, taramayı hiçbir zaman sıfırdan yeniden başlatmamıza gerek olmadığıdır; Halihazırda topladığımız yararlı bilgileri saklıyoruz ve bunları aşamalı olarak ayarlıyoruz.
Kabaca sayın.
“(1) kayan2 pencere3 sihir değildir;5 sadece 6 sadece7 a8 disiplinli9 yol10 ila 11 yeniden kullanım12 çalışmasıdır.13 Hayal edin14 siz15’in16 a17 işaretçisi18 çifti, 19 sol20 ve21 sağ,22 bu23 sınırlandırma24 a25 alt dizesi var.26 As27 siz28 genişletin29 sağa,30 siz31 güncelleme32 bazı33 durum34 (gibi35) a36 sıklık37 haritası).38 Ne zaman3940 penceresi4143 kısıtlamayı44 ihlal ederse (çok45 çok46 farklı47 karakter,48 toplam49 çok50 büyük,51 vb.),52 sen53 hareket54 sola55 ileri,56 daraltma5758 pencere59 ve6062 durumunu63 tekrar güncelle.64 Çünkü65 her66 dizin6768 ziyaret69’de70 ay t71 iki kez—bir kez72 x73 sağa,74 kez75 x76 sola—77 toplam78 çalışır79 kalır80 doğrusal.81 Neden8283 bu8485 O(n) verir?86 Her87 öğe888990 penceresine91 tam olarak92 kez93 ne zaman94 sağa95 hareket eder96 ileri gider,97 ve9899’dan tam olarak100 kez101 ne zaman102 sola103 hamle104 ileri.105 No106 element107 is108 işlendi109 daha fazla110’dan111 a112 sabit113 sayı114 of115 kere,116 so117 toplam118 operasyon120121 orantılı122 -123 n.124 The125 içgörü126 is127 that128 we129 asla130 131 ila 132 yeniden başlatma133 the134 tarama135 sıfırdan 136;137 we138 tutma139 the140 yararlı141 bilgi142 biz143 zaten144 toplandı145 ve146 ayarlama147 it148 artımlı149.” Yaklaşık 149 kelime.
Gücü Kullanmak (Kod ve Örnekler) Problem 1: En Fazla K Farklı Karaktere Sahip En Uzun Alt Dizi Kaba kuvvet (tuzak) piton def en uzun_substring_brute(s, k): n = uzunluk(lar) en iyi = 0 (n) aralığındaki i için: frekans = {} farklı = 0 (i, n) aralığındaki j için: ch = s[j] eğer kanal frekansta değilse: frekans[kanal] = 0 farklı += 1 frekans[kanal] += 1
İlgili yazılar
Ek okuma: MDN Web Docs
Editörün Notu
Kayan pencere yöntemi, algoritma verimliliğini artırmak için gereksiz hesaplamalardan kaçınarak işlem süresini önemli ölçüde azaltır; bu yaklaşımı öğrenmek, büyük veri setlerinde performansı optimize etmek isteyenler için kritik bir beceridir.
