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 una volta, e usa uno spazio aggiuntivo O(1) : un contatore per la sequenza corrente e uno per la migliore. Riavviare il conteggio a ogni indice richiede O(n²) su un array composto interamente da 1.

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

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

Q: Il problema del numero massimo di 1 consecutivi si risolve con la tecnica della finestra scorrevole?

Puoi considerarla come una finestra: la finestra contiene la sequenza corrente, il suo bordo destro si sposta a ogni valore e uno 0 sposta il bordo sinistro oltre di esso. La finestra non si restringe mai passo dopo passo, quindi un contatore sostituisce i due bordi.

PrincipianteArray e stringhe

+10

Ti viene dato un array nums in cui ogni valore è 0 o 1. Una serie è una sequenza di 1 adiacenti, senza 0 in mezzo. Restituisci la lunghezza della serie 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 serie più lunga di 1 consecutivi

Vincoli

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

Esempi

Input: nums = [1, 1, 0, 1, 1, 1, 0, 1]
Output: 3
Spiegazione: Gli 1 formano tre sequenze: dagli indici 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: Il singolo 1 all'indice 1 perde contro la coppia agli indici 3 e 4, quindi la risposta è 2.

Input: nums = [0, 0, 0]
Output: 0
Spiegazione: Non c'è alcun 1, quindi non c'è nessuna sequenza e la risposta è 0.

Per approfondire

E se potessi trasformare fino a k zeri in uno? Quanto può diventare lunga la sequenza più lunga 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 a ogni indice ti serve solo la lunghezza della sequenza che termina lì. Un contatore che aumenta con un 1 e si azzera con uno 0 trova la sequenza più lunga in un unico passaggio.

Conta in avanti da ogni indice

Corretto, ma non termina sui test più grandi

Intuizione

Prova ogni indice come punto di partenza e procedi in avanti finché trovi degli 1; il numero di passi è la lunghezza della sequenza che inizia da lì. La sequenza più lunga inizia in uno di questi indici, quindi il conteggio più alto è la risposta.

Le scansioni si sovrappongono. Su un array di n uni, richiedono circa n² / 2 passi, 2 × 10^8 per n = 2 × 10^4.

Algoritmo

Imposta best = 0.
Per ogni indice start, imposta length = 0.
Mentre start + length è all'interno dell'array e nums[start + length] è 1, aggiungi 1 a length.
Mantieni il valore più grande 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 conteggio progressivo

Intuizione

Mantieni current, la lunghezza della sequenza di 1 che termina all'indice in cui ti trovi. Un 1 allunga la sequenza di uno; uno 0 la termina, quindi current scende a 0. Ogni sequenza viene misurata al suo ultimo indice, dove current è uguale alla sua lunghezza completa, quindi il valore massimo raggiunto da current è la risposta.

Con [1, 1, 0, 1, 1, 1, 0, 1], current assume i valori 1, 2, 0, 1, 2, 3, 0, 1 e il valore massimo è 3.

Algoritmo

Imposta best = 0 e current = 0.
Per ogni valore in nums: se è 1, aggiungi 1 a current e mantieni il valore 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

Aggiornare best solo quando incontri uno 0. Una sequenza che arriva alla fine, come in [0, 1, 1], non viene mai registrata. Aggiorna dopo ogni 1 oppure confronta ancora una volta dopo il ciclo.
Non azzerare current quando incontri uno 0. Le sequenze separate si sommano e [1, 1, 0, 1, 1] restituisce 4.
Iniziare best da 1 o da nums[0]. [0, 0, 0] deve restituire 0.
In Lua e R, dove gli array iniziano da 1, delimitare la scansione in avanti con < n invece di ≤ n. L’ultimo valore non viene mai letto, quindi [0, 1] restituisce 0.

Domande frequenti3

Qual è la complessità temporale di Max Consecutive Ones?

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

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

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

Il problema del numero massimo di 1 consecutivi si risolve con la tecnica della finestra scorrevole?

Puoi considerarla come una finestra: la finestra contiene la sequenza corrente, il suo bordo destro si sposta a ogni valore e uno 0 sposta il bordo sinistro oltre di esso. La finestra non si restringe mai passo dopo passo, quindi un contatore sostituisce i due bordi.

def findMaxConsecutiveOnes(nums):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso