Tell vinduer som oppfyller en regel
Trikset at most-K minus at most-(K-1)
Tell vinduer som oppfyller en regel er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Tell, ikke mål
Noen ganger må du telle delarrayer som oppfyller en regel, i stedet for å finne det lengste. Et lite triks gjør dette til en enkel oppgave for skyvevindu. 🔢
Utfordringen med nøyaktig K
Det er vanskelig å telle delarrayer med nøyaktig K av noe direkte. Grensen skifter hele tiden, noe som gjør ett enkelt vindu vanskelig å bruke.
Omformuler til høyst
Det er mye enklere å telle delarrayer med høyst K ved hjelp av ett vindu. Når du utvider mot høyre, gir hver gyldige start ett delarray som skal telles.
Subtraksjonstrikset
Nøyaktig K er lik atMost(K) minus atMost(K - 1). To enkle opptellinger kombineres til den vanskelige opptellingen du faktisk trenger.
answer = at_most(k) - at_most(k - 1)Lag hjelpefunksjonen
Skriv én funksjon som teller delarrayer med høyst k. Den skyver et vindu og krymper det når antallet overstiger k.
def at_most(k):
left = 0
total = 0Krymp når regelen brytes
Utvid mot høyre og oppdater vinduet. Så lenge det inneholder mer enn k, flytter du left fremover for å få det innenfor grensen igjen.
while count > k:
# remove a[left]
left += 1Legg til antallet i vinduet
Når vinduet er korrigert, er alle delarrayer som ender på right og starter fra left og videre, gyldige. Legg til right minus left pluss én.
total += right - left + 1Hvorfor denne opptellingen fungerer
For en fast right er de gyldige startene left, left+1 og så videre opp til right. Det er nøyaktig right - left + 1 delarrayer, og alle oppfyller kravet om høyst k.
Kombiner de to kallene
Kjør hjelpefunksjonen to ganger og trekk fra. Hvert kall er O(n), så den fullstendige opptellingen av nøyaktig K er fortsatt lineær.
return at_most(k) - at_most(k - 1)Håndter grenseverdien
Når k er null, vil atMost(k - 1) bruke negativ én. Håndter dette tilfellet, slik at hjelpefunksjonen fortsatt returnerer en fornuftig opptelling på null.
Når metoden kan brukes
Ideen høyst minus høyst passer når du skal telle delarrayer med nøyaktig K ulike verdier, K oddetall eller en annen monoton egenskap for hvert vindu.
Rask kontroll
Du vil telle delarrayer med nøyaktig K ulike elementer.
Oppsummering
Å telle nøyaktig K betyr ganske enkelt atMost(K) minus atMost(K - 1). Hver hjelpefunksjon skyver et vindu i O(n), så hele opptellingen forblir lineær. ✅
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Tell vinduer som oppfyller en regel» gratis?
Ja – hele teksten i «Tell vinduer som oppfyller en regel» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Tell vinduer som oppfyller en regel»?
Trikset at most-K minus at most-(K-1) Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.
Hvor lang tid tar leksjonen «Tell vinduer som oppfyller en regel»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Summer i vinduer med fast størrelse
- Variabelt vindu med to pekere
- Lengste delstreng uten gjentakelser
- Tell vinduer som oppfyller en regel