Max Consecutive Ones

Q: Jaka jest złożoność czasowa problemu Max Consecutive Ones?

Rozwiązanie wykonujące jedno przejście działa w czasie O(n) , ponieważ odczytuje każdą wartość raz, i wykorzystuje O(1) dodatkowej przestrzeni: jeden licznik bieżącej serii i jeden najlepszej. Ponowne rozpoczynanie liczenia przy każdym indeksie zajmuje O(n²) w przypadku tablicy zawierającej same jedynki.

Q: Dlaczego licznik resetuje się do 0 zamiast do 1?

Licznik przechowuje długość ciągu kończącego się na bieżącym indeksie. Gdy wartość w tym miejscu wynosi 0 , nie kończy się tam żaden ciąg jedynek, więc jego długość wynosi 0 . Następna jedynka zwiększa tę wartość do 1 — długości nowego ciągu.

Q: Czy problem „Maksymalna liczba kolejnych jedynek” można rozwiązać za pomocą metody przesuwnego okna?

Możesz postrzegać je jako jedno: okno przechowuje bieżący ciąg, jego prawa krawędź przesuwa się przy każdej wartości, a 0 przesuwa lewą krawędź poza nią. Okno nigdy nie zmniejsza się krok po kroku, więc jeden licznik zastępuje dwie krawędzie.

PoczątkującyTablice i napisy

+10

Otrzymujesz tablicę nums, w której każda wartość to 0 albo 1. Seria to ciąg jedynek znajdujących się obok siebie, bez żadnego 0 pomiędzy nimi. Zwróć długość najdłuższej serii albo 0, jeśli tablica nie zawiera żadnej jedynki.

Funkcja

findMaxConsecutiveOnes(nums: integer-array) → integer

numsinteger-array: tablica zer i jedynek
Zwracainteger: długość najdłuższej serii kolejnych jedynek

Ograniczenia

1 ≤ nums.length ≤ 2 × 10⁴
Każde nums[i] ma wartość 0 lub 1.

Przykłady

Wejście: nums = [1, 1, 0, 1, 1, 1, 0, 1]
Wyjście: 3
Wyjaśnienie: Jedynki tworzą trzy serie: indeksy 0 do 1 (długość 2), 3 do 5 (długość 3) oraz sam indeks 7 (długość 1). Najdłuższa ma długość 3.

Wejście: nums = [0, 1, 0, 1, 1]
Wyjście: 2
Wyjaśnienie: Pojedyncza 1 na indeksie 1 przegrywa z parą na indeksach 3 i 4, więc odpowiedzią jest 2.

Wejście: nums = [0, 0, 0]
Wyjście: 0
Wyjaśnienie: Nigdzie nie ma 1, więc nie ma serii, a odpowiedź to 0.

Pytanie dodatkowe

Co jeśli możesz zamienić maksymalnie k zer na jedynki? Jak długa może być najdłuższa seria i czy nadal możesz ją znaleźć w jednym przebiegu?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Seria kończy się w chwili, gdy pojawi się 0, więc dla każdego indeksu wystarczy znać długość serii kończącej się w tym miejscu. Jeden licznik, który zwiększa się przy 1 i zeruje przy 0, pozwala znaleźć najdłuższą serię w jednym przebiegu.

Liczenie w przód od każdego indeksu

Poprawne, ale nie kończy się na największych testach

Intuicja

Wypróbuj każdy indeks jako początek i idź do przodu, dopóki widzisz jedynki; liczba kroków to długość serii rozpoczynającej się w tym miejscu. Najdłuższa seria zaczyna się pod jednym z tych indeksów, więc największa liczba to odpowiedź.

Te przejścia nakładają się na siebie. W tablicy złożonej z n jedynek wykonują około n² / 2 kroków, czyli 2 × 10^8 dla n = 2 × 10^4.

Algorytm

Ustaw best = 0.
Dla każdego indeksu start ustaw length = 0.
Gdy start + length znajduje się w tablicy, a nums[start + length] ma wartość 1, zwiększ length o 1.
Wybierz większą wartość spośród best i length.
Zwróć 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

Jedno przejście z bieżącym licznikiem

Intuicja

Przechowuj w current długość ciągu jedynek kończącego się na indeksie, na którym jesteś. Jedynka wydłuża ten ciąg o jeden, a zero go kończy, więc current spada do 0. Każdy ciąg jest mierzony na swoim ostatnim indeksie, gdzie current jest równy jego pełnej długości, więc największa wartość osiągana przez current jest odpowiedzią.

Dla [1, 1, 0, 1, 1, 1, 0, 1] current przyjmuje wartości 1, 2, 0, 1, 2, 3, 0, 1, a największą z nich jest 3.

Algorytm

Ustaw best = 0 i current = 0.
Dla każdej wartości w nums: jeśli wynosi 1, dodaj 1 do current i zachowaj większą z wartości best i current.
Jeśli wynosi 0, ustaw current = 0.
Zwróć 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

Pułapki i przypadki brzegowe

Aktualizowanie best tylko wtedy, gdy napotkasz 0. Seria sięgająca końca, jak w [0, 1, 1], nigdy nie zostanie odnotowana. Aktualizuj wartość po każdym 1 albo porównaj ją jeszcze raz po pętli.
Niezerowanie current po napotkaniu 0. Oddzielne serie sumują się, a [1, 1, 0, 1, 1] zwraca 4.
Ustawianie początkowej wartości best na 1 lub nums[0]. [0, 0, 0] musi zwrócić 0.
W Lua i R, gdzie indeksowanie tablic zaczyna się od 1, ograniczanie przejścia do przodu warunkiem < n zamiast ≤ n. Ostatnia wartość nigdy nie jest odczytywana, więc [0, 1] zwraca 0.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu Max Consecutive Ones?

Rozwiązanie wykonujące jedno przejście działa w czasie O(n), ponieważ odczytuje każdą wartość raz, i wykorzystuje O(1) dodatkowej przestrzeni: jeden licznik bieżącej serii i jeden najlepszej. Ponowne rozpoczynanie liczenia przy każdym indeksie zajmuje O(n²) w przypadku tablicy zawierającej same jedynki.

Dlaczego licznik resetuje się do 0 zamiast do 1?

Licznik przechowuje długość ciągu kończącego się na bieżącym indeksie. Gdy wartość w tym miejscu wynosi 0, nie kończy się tam żaden ciąg jedynek, więc jego długość wynosi 0. Następna jedynka zwiększa tę wartość do 1 — długości nowego ciągu.

Czy problem „Maksymalna liczba kolejnych jedynek” można rozwiązać za pomocą metody przesuwnego okna?

Możesz postrzegać je jako jedno: okno przechowuje bieżący ciąg, jego prawa krawędź przesuwa się przy każdej wartości, a 0 przesuwa lewą krawędź poza nią. Okno nigdy nie zmniejsza się krok po kroku, więc jeden licznik zastępuje dwie krawędzie.

def findMaxConsecutiveOnes(nums):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

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

Oczekiwany wynik