Max Consecutive Ones

Q: Qual è la complessità temporale di Max Consecutive Ones?

La soluzione in un solo passaggio richiede un tempo O(n) , perché legge ogni valore esattamente una volta. Usa uno spazio aggiuntivo O(1) : un contatore per la serie corrente e uno per la migliore. Riavviare il conteggio a ogni indice richiede un tempo O(n²) su un array composto solo da 1.

Q: Perché il contatore si azzera a 0 invece che a 1?

Il contatore contiene la lunghezza della sequenza che termina all’indice corrente. Quando il valore corrente è 0 , nessuna sequenza di 1 termina lì, quindi la sua lunghezza è 0 . Il successivo 1 lo porta a 1 , che è la lunghezza corretta di una nuova sequenza.

Q: È un problema di finestra scorrevole?

Puoi vederla come una finestra: contiene la sequenza corrente, il bordo destro si sposta a ogni valore e uno 0 fa avanzare il bordo sinistro oltre di sé. Qui non è mai necessario restringere la finestra passo dopo passo, quindi un unico contatore sostituisce i due bordi. La visualizzazione come finestra torna utile nella versione più difficile, in cui puoi trasformare fino a k zeri in uni.

Q: Come si contano gli 1 consecutivi se puoi trasformare uno 0?

Mantieni due contatori: la lunghezza della sequenza che termina qui senza inversioni e quella con un'inversione già usata. Con un 1, entrambi aumentano di uno. Con uno 0, il contatore con inversione diventa il contatore senza inversione più uno, e il contatore senza inversione si azzera. La risposta è il valore massimo del contatore con inversione che trovi, sempre in un'unica passata.

PrincipianteArray e stringhe

+10

Ricevi un array nums in cui ogni valore è 0 o 1. Una sequenza è una serie di 1 consecutivi, senza 0 tra di loro. Restituisci la lunghezza della sequenza più lunga, oppure 0 se l'array non contiene alcun 1.

Funzione

findMaxConsecutiveOnes(nums: integer-array) → integer

numsinteger-array: un array di 0 e 1
Restituisceinteger: la lunghezza della sequenza più lunga di 1 consecutivi

Vincoli

1 ≤ nums.length ≤ 2 × 10⁴
Ogni nums[i] è 0 oppure 1.

Esempi

Input: nums = [1, 1, 0, 1, 1, 1, 0, 1]
Output: 3
Spiegazione: Gli 1 formano tre sequenze consecutive: gli indici da 0 a 1 (lunghezza 2), da 3 a 5 (lunghezza 3) e l’indice 7 da solo (lunghezza 1). La più lunga ha lunghezza 3.

Input: nums = [0, 1, 0, 1, 1]
Output: 2
Spiegazione: Le sequenze sono il singolo 1 all'indice 1 e la coppia agli indici 3 e 4. Vince la coppia con lunghezza 2.

Input: nums = [0, 0, 0]
Output: 0
Spiegazione: Non c'è nessun 1, quindi non c'è alcuna serie e la risposta è 0.

+14 test nascosti all’invio

Per approfondire

Che cosa succede se puoi trasformare fino a k zeri in uni? Quanto può diventare lunga la sequenza più lunga di 1 e riesci ancora a trovarla in un solo passaggio?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Una sequenza termina nel momento in cui compare uno 0, quindi l’unica cosa che devi sapere in ogni indice è quanto è lunga la sequenza che termina lì. Ricominciare a contare da zero a ogni indice ripete lo stesso lavoro ancora e ancora. Un contatore che aumenta con un 1 e si azzera con uno 0 risponde alla domanda in un’unica passata.

Conta in avanti da ogni indice

Corretto, ma non termina sui test più grandi

Intuizione

Ogni sequenza inizia da qualche parte. Prova quindi ogni indice come punto di partenza e procedi in avanti finché continui a incontrare degli 1; il numero di passi è la lunghezza della sequenza che inizia lì. Il conteggio più alto tra tutti i punti di partenza è la risposta. Per [1, 1, 0, 1, 1, 1, 0, 1], partendo dall'indice 3 si incontrano tre 1 prima di raggiungere lo 0 all'indice 6, ottenendo 3.

La risposta è corretta perché la sequenza più lunga inizia in uno degli indici che provi e, partendo dal suo primo indice, il percorso ne misura esattamente la lunghezza.

Il costo si nasconde nelle sovrapposizioni. In un array di n 1, partendo dall'indice 0 si percorrono n passi, dal successivo n-1 e così via, per un totale di circa n² / 2 passi. Per n = 2 × 10^4 sono 2 × 10^8 passi, troppi per il limite di tempo nei linguaggi più lenti.

Algoritmo

Imposta best = 0.
Per ogni indice start, imposta length = 0.
Finché start + length è all'interno dell'array e nums[start + length] è 1, aggiungi 1 a length.
Conserva il maggiore tra best e length.
Restituisci best.

def findMaxConsecutiveOnes(nums):
    n = len(nums)
    best = 0
    for start in range(n):
        length = 0
        while start + length < n and nums[start + length] == 1:
            length += 1
        best = max(best, length)
    return best

Un passaggio con un conteggio progressivo

Intuizione

Scorri l’array una volta e mantieni current, la lunghezza della sequenza di 1 che termina all’indice in cui ti trovi. Un 1 prolunga quella sequenza, quindi current aumenta di uno. Uno 0 la interrompe, quindi current torna a 0. Dopo ogni 1, confronta current con best.

Con [1, 1, 0, 1, 1, 1, 0, 1], current assume i valori 1, 2, 0, 1, 2, 3, 0, 1, e il più grande è 3. Ogni sequenza viene misurata al suo ultimo indice, dove current è uguale alla sua lunghezza totale, quindi il valore migliore osservato è la sequenza più lunga.

Ogni valore viene letto una volta, con una complessità temporale di O(n), e ti bastano due interi per la memoria.

Algoritmo

Imposta best = 0 e current = 0.
Per ogni valore in nums: se è 1, aggiungi 1 a current e mantieni il maggiore tra best e current.
Se è 0, imposta current = 0.
Restituisci best.

def findMaxConsecutiveOnes(nums):
    best = 0
    current = 0
    for x in nums:
        if x == 1:
            current += 1
            best = max(best, current)
        else:
            # A 0 breaks the run.
            current = 0
    return best

Trappole e casi limite

La versione a passaggio singolo è breve, quindi gli errori derivano dal momento in cui aggiorni la risposta.

Aggiornare best solo quando incontri uno 0. Una sequenza che raggiunge la fine dell'array, come in [0, 1, 1], non viene mai registrata. Aggiorna dopo ogni 1 oppure confronta ancora una volta dopo il ciclo.
Dimenticare di reimpostare current su uno 0, sommando così gli 1 di sequenze separate e restituendo 4 per [1, 1, 0, 1, 1].
Inizializzare best a 1 o a nums[0]. Un array composto solo da 0 deve restituire 0.
In Lua e R l'array inizia dall'indice 1, quindi l'iterazione in avanti verifica start + length ≤ n invece di < n.

Domande frequenti4

Qual è la complessità temporale di Max Consecutive Ones?

La soluzione in un solo passaggio richiede un tempo O(n), perché legge ogni valore esattamente una volta. Usa uno spazio aggiuntivo O(1): un contatore per la serie corrente e uno per la migliore. Riavviare il conteggio a ogni indice richiede un tempo O(n²) su un array composto solo da 1.

Perché il contatore si azzera a 0 invece che a 1?

Il contatore contiene la lunghezza della sequenza che termina all’indice corrente. Quando il valore corrente è 0, nessuna sequenza di 1 termina lì, quindi la sua lunghezza è 0. Il successivo 1 lo porta a 1, che è la lunghezza corretta di una nuova sequenza.

È un problema di finestra scorrevole?

Puoi vederla come una finestra: contiene la sequenza corrente, il bordo destro si sposta a ogni valore e uno 0 fa avanzare il bordo sinistro oltre di sé. Qui non è mai necessario restringere la finestra passo dopo passo, quindi un unico contatore sostituisce i due bordi. La visualizzazione come finestra torna utile nella versione più difficile, in cui puoi trasformare fino a k zeri in uni.

Come si contano gli 1 consecutivi se puoi trasformare uno 0?

Mantieni due contatori: la lunghezza della sequenza che termina qui senza inversioni e quella con un'inversione già usata. Con un 1, entrambi aumentano di uno. Con uno 0, il contatore con inversione diventa il contatore senza inversione più uno, e il contatore senza inversione si azzera. La risposta è il valore massimo del contatore con inversione che trovi, sempre in un'unica passata.

Python

def findMaxConsecutiveOnes(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

nums = [1, 1, 0, 1, 1, 1, 0, 1]

Atteso