Zliczanie okien spełniających regułę
Sztuczka: co najwyżej K minus co najwyżej (K-1)
Zliczanie okien spełniających regułę 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.
Zliczanie zamiast mierzenia
Czasami trzeba zliczyć podtablice spełniające regułę, a nie znaleźć najdłuższą z nich. Prosta sztuczka zamienia to w łatwe zadanie z oknem przesuwnym. 🔢
Wyzwanie dokładnie K
Bezpośrednie zliczanie podtablic zawierających dokładnie K wystąpień czegoś jest kłopotliwe. Granica ciągle się zmienia, przez co trudno utworzyć jedno proste okno.
Przeformułowanie na co najwyżej
Zliczanie podtablic zawierających co najwyżej K elementów jest znacznie łatwiejsze przy użyciu jednego okna. Podczas rozszerzania go w prawo każde poprawne left wyznacza podtablicę, którą należy zliczyć.
Sztuczka z odejmowaniem
Dokładnie K oznacza atMost(K) minus atMost(K - 1). Dwa łatwe zliczenia dają w połączeniu trudny wynik, którego rzeczywiście potrzebujemy.
answer = at_most(k) - at_most(k - 1)Budowa funkcji pomocniczej
Należy napisać jedną funkcję zliczającą podtablice zawierające co najwyżej k elementów. Funkcja przesuwa okno i zmniejsza je, gdy liczba przekroczy k.
def at_most(k):
left = 0
total = 0Zmniejszanie po naruszeniu reguły
Należy rozszerzać okno wskaźnikiem right i aktualizować jego stan. Gdy zawiera więcej niż k elementów, trzeba przesuwać left do przodu, aby przywrócić poprawny zakres.
while count > k:
# remove a[left]
left += 1Dodanie liczby podtablic okna
Po naprawieniu okna każda podtablica kończąca się na right i rozpoczynająca się od left lub dalej jest poprawna. Należy dodać right minus left plus jeden.
total += right - left + 1Dlaczego to zliczanie działa
Dla ustalonego right poprawne początki to left, left+1 aż do right. Daje to dokładnie right - left + 1 podtablic, z których każda spełnia warunek at-most-k.
Połączenie dwóch wywołań
Należy dwukrotnie uruchomić funkcję pomocniczą i odjąć wyniki. Każde wywołanie ma koszt O(n), więc pełne zliczanie dokładnie-K nadal działa w czasie liniowym.
return at_most(k) - at_most(k - 1)Obsługa przypadku brzegowego
Gdy k wynosi zero, atMost(k - 1) używałoby wartości minus jeden. Należy obsłużyć ten przypadek, aby funkcja pomocnicza nadal zwracała sensowny wynik równy zero.
Zastosowania
Pomysł at-most minus at-most pasuje do zliczania podtablic zawierających dokładnie K różnych wartości, K liczb nieparzystych lub dowolną monotoniczną właściwość okna.
Szybkie sprawdzenie
Należy zliczyć podtablice zawierające dokładnie K różnych elementów.
Podsumowanie
Zliczanie dokładnie K to po prostu atMost(K) minus atMost(K - 1). Każda funkcja pomocnicza przesuwa okno w czasie O(n), więc całe zliczanie pozostaje liniowe. ✅
Ucz się Coding Interview Prep dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 90
- Lekcje
- 360
Często zadawane pytania
Czy lekcja „Zliczanie okien spełniających regułę” jest bezpłatna?
Tak — pełny tekst „Zliczanie okien spełniających regułę” 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 „Zliczanie okien spełniających regułę”?
Sztuczka: co najwyżej K minus co najwyżej (K-1) Ć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 „Zliczanie okien spełniających regułę”?
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
- Sumy okien o stałym rozmiarze
- Zmienny zakres okna z dwoma wskaźnikami
- Najdłuższy podnapis bez powtórzeń
- Zliczanie okien spełniających regułę