Tæl vinduer, der opfylder en regel
Tricket med højst-K minus højst-(K-1)
Tæl vinduer, der opfylder en regel er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
At tælle, ikke måle
Nogle gange skal du tælle delarrays, der opfylder en regel, i stedet for at finde det længste. Et lille trick gør det til let arbejde med glidende vinduer. 🔢
Udfordringen med præcis K
Det er besværligt direkte at tælle delarrays med præcis K af noget. Grænsen skifter hele tiden, så det er svært at lave ét enkelt, rent vindue.
Tænk i højst
At tælle delarrays med højst K er meget lettere med ét vindue. Når du udvider mod højre, giver hver gyldig left et delarray, der skal tælles.
Tricket med subtraktion
Præcis K er lig med atMost(K) minus atMost(K - 1). To enkle optællinger kombineres til den vanskelige optælling, du faktisk har brug for.
answer = at_most(k) - at_most(k - 1)Byg hjælpefunktionen
Skriv én funktion, der tæller delarrays med højst k. Den flytter et vindue og formindsker det, hver gang antallet overstiger k.
def at_most(k):
left = 0
total = 0Formindsk ved overtrædelse
Udvid mod højre, og opdatér vinduet. Mens det indeholder mere end k, skal du flytte left fremad for at bringe det tilbage inden for grænsen.
while count > k:
# remove a[left]
left += 1Læg vinduets antal til
Når vinduet er rettet, er hvert delarray, der slutter ved right og har et startpunkt fra left og frem, gyldigt. Læg right minus left plus one til.
total += right - left + 1Hvorfor optællingen virker
For et fast right er de gyldige startpunkter left, left+1, op til right. Det er præcis right - left + 1 delarrays, som alle opfylder kravet om højst k.
Kombinér de to kald
Kør hjælpefunktionen to gange, og træk fra. Hvert kald er O(n), så den samlede optælling for præcis K er stadig lineær.
return at_most(k) - at_most(k - 1)Håndtér randtilfældet
Når k er nul, ville atMost(k - 1) bruge minus én. Håndtér det, så hjælpefunktionen stadig returnerer et fornuftigt antal på nul.
Hvor det kan bruges
Denne idé med højst minus højst passer til optælling af delarrays med præcis K forskellige værdier, K ulige tal eller en vilkårlig monoton egenskab for hvert vindue.
Hurtigt tjek
Du vil tælle delarrays med præcis K forskellige elementer.
Opsummering
At tælle præcis K er blot atMost(K) minus atMost(K - 1). Hver hjælpefunktion flytter et vindue i O(n), så hele optællingen forbliver lineær. ✅
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Tæl vinduer, der opfylder en regel” gratis?
Ja — hele teksten til “Tæl vinduer, der opfylder en regel” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Tæl vinduer, der opfylder en regel”?
Tricket med højst-K minus højst-(K-1) Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.
Hvor lang tid tager lektionen “Tæl vinduer, der opfylder en regel”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Summer i vinduer med fast størrelse
- Variabelt vindue med to pointere
- Længste substring uden gentagelser
- Tæl vinduer, der opfylder en regel