Contare le finestre che soddisfano una regola
Il trucco: al più K meno al più (K-1)
Contare le finestre che soddisfano una regola è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Contare, non misurare
A volte è necessario contare i sottoarray che soddisfano una regola, non trovare quello più lungo. Un piccolo trucco trasforma il problema in un semplice esercizio sulle finestre scorrevoli. 🔢
La difficoltà di esattamente K
Contare direttamente i sottoarray con esattamente K occorrenze di qualcosa è complicato. Il confine continua a cambiare, rendendo difficile usare un'unica finestra semplice.
Riformulare come al più
Contare i sottoarray con al più K elementi è molto più semplice usando un'unica finestra. Espandendo right, ogni possibile left produce un sottoarray da contare.
Il trucco della sottrazione
Esattamente K equivale a atMost(K) meno atMost(K - 1). Due conteggi semplici si combinano per ottenere quello complesso che interessa davvero.
answer = at_most(k) - at_most(k - 1)Costruire la funzione di supporto
Scriva una funzione che conti i sottoarray con al più k elementi. La funzione fa scorrere una finestra e la restringe ogni volta che il conteggio supera k.
def at_most(k):
left = 0
total = 0Restringere in caso di violazione
Espanda right e aggiorni la finestra. Finché contiene più di k elementi, faccia avanzare left per riportarla nell'intervallo consentito.
while count > k:
# remove a[left]
left += 1Aggiungere il conteggio della finestra
Dopo aver sistemato la finestra, ogni sottoarray che termina in right e ha un inizio da left in poi è valido. Aggiunga right meno left più uno.
total += right - left + 1Perché questo conteggio funziona
Per un right fisso, gli inizi validi sono left, left+1 e così via fino a right. Si tratta esattamente di right - left + 1 sottoarray, tutti validi secondo la condizione al più k.
Combinare le due chiamate
Esegua due volte la funzione di supporto e sottragga i risultati. Ogni chiamata è O(n), quindi il conteggio completo di esattamente K rimane lineare.
return at_most(k) - at_most(k - 1)Gestire il caso limite
Quando k è zero, atMost(k - 1) userebbe meno uno. Gestisca questo caso, così la funzione di supporto restituirà comunque un conteggio sensato pari a zero.
Dove si applica
L'idea al più meno al più è adatta a contare i sottoarray con esattamente K valori distinti, K numeri dispari o qualsiasi proprietà monotona della finestra.
Verifica rapida
Desidera contare i sottoarray con esattamente K elementi distinti.
Riepilogo
Contare esattamente K significa semplicemente calcolare atMost(K) meno atMost(K - 1). Ogni funzione di supporto fa scorrere una finestra in O(n), quindi il conteggio complessivo rimane lineare. ✅
Impara Coding Interview Prep con un tutor IA — gratis
Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.
- Corsi
- 90
- Lezioni
- 360
Domande Frequenti
La lezione «Contare le finestre che soddisfano una regola» è gratuita?
Sì — il testo completo di «Contare le finestre che soddisfano una regola» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Contare le finestre che soddisfano una regola»?
Il trucco: al più K meno al più (K-1) Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Contare le finestre che soddisfano una regola»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Somme su finestre di dimensione fissa
- Finestra variabile con due puntatori
- Sottostringa più lunga senza ripetizioni
- Contare le finestre che soddisfano una regola