Max Consecutive Ones

Q: Jaka jest złożoność czasowa zadania „Maksymalna liczba kolejnych jedynek”?

Rozwiązanie przechodzące przez tablicę jeden raz działa w czasie O(n) , ponieważ odczytuje każdą wartość dokładnie raz. Używa O(1) dodatkowej pamięci: jednego licznika bieżącej serii i jednego licznika najlepszego wyniku. Rozpoczynanie liczenia od nowa przy każdym indeksie zajmuje O(n²) czasu w przypadku tablicy składającej się wyłącznie z 1.

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

Licznik przechowuje długość serii kończącej się na bieżącym indeksie. Gdy bieżąca wartość wynosi 0 , nie kończy się tam żadna seria jedynek, więc jej długość wynosi 0 . Następna jedynka zwiększa ją do 1 , co jest prawidłową długością nowej serii.

Q: Czy to problem z oknem przesuwnym?

Możesz potraktować to jako jedno: okno przechowuje bieżący ciąg, prawa krawędź przesuwa się przy każdej wartości, a 0 przesuwa lewą krawędź za siebie. Tutaj okno nigdy nie musi się zmniejszać krok po kroku, więc pojedynczy licznik zastępuje obie krawędzie. Widok z oknem przydaje się w trudniejszej wersji, w której możesz zamienić maksymalnie k zer na jedynki.

Q: Jak policzyć kolejne jedynki, jeśli możesz zmienić jedno 0?

Prowadź dwa liczniki: długość ciągu kończącego się tutaj bez zmiany oraz długość ciągu, w którym wykorzystano już jedną zmianę. Przy 1 oba zwiększają się o jeden. Przy 0 licznik ciągu ze zmianą przyjmuje wartość zwykłego licznika plus jeden, a zwykły licznik resetuje się do 0. Odpowiedzią jest największa wartość licznika ciągu ze zmianą, jaką zobaczysz, nadal w jednym przebiegu.

PoczątkującyTablice i napisy

+10

Otrzymujesz tablicę nums, w której każda wartość to 0 lub 1. Seria to ciąg sąsiadujących ze sobą jedynek, między którymi nie ma 0. 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] jest równe 0 lub 1.

Przykłady

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

Wejście: nums = [0, 1, 0, 1, 1]
Wyjście: 2
Wyjaśnienie: Serie to pojedyncza 1 na indeksie 1 oraz para na indeksach 3 i 4. Wygrywa para o długości 2.

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

+14 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Co jeśli możesz zamienić maksymalnie k zer na jedynki? Jak długa może być najdłuższa seria jedynek 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 jedyne, co musisz wiedzieć dla każdego indeksu, to jak długa jest kończąca się tam seria. Liczenie od początku dla każdego indeksu powoduje wielokrotne powtarzanie tej samej pracy. Jeden licznik, który zwiększa się przy 1 i zeruje przy 0, odpowiada na to pytanie w jednym przebiegu.

Licz w przód od każdego indeksu

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

Intuicja

Każda seria ma jakiś początek. Spróbuj więc każdego indeksu jako początku i idź dalej, dopóki widzisz jedynki; liczba kroków to długość serii, która zaczyna się w tym miejscu. Największa liczba spośród wszystkich początków jest odpowiedzią. Dla [1, 1, 0, 1, 1, 1, 0, 1] początek pod indeksem 3 pozwala przejść przez trzy jedynki, zanim napotkasz 0 pod indeksem 6, co daje wynik 3.

Odpowiedź jest poprawna, ponieważ najdłuższa seria zaczyna się pod jednym ze sprawdzanych indeksów, a przejście od jej pierwszego indeksu mierzy ją dokładnie.

Koszt kryje się w nakładaniu się przejść. W tablicy złożonej z n jedynek początek pod indeksem 0 wymaga przejścia n kroków, kolejny n-1 kroków i tak dalej — łącznie około n² / 2 kroków. Dla n = 2 × 10^4 to 2 × 10^8 kroków, czyli za dużo, by zmieścić się w limicie czasu w wolniejszych językach.

Algorytm

Ustaw best = 0.
Dla każdego indeksu start ustaw length = 0.
Dopóki start + length znajduje się w tablicy, a nums[start + length] ma wartość 1, zwiększaj length o 1.
Zachowaj większą z wartości 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

Przejdź raz przez tablicę i przechowuj current, czyli długość ciągu jedynek kończącego się na indeksie, na którym jesteś. Jedynka wydłuża ten ciąg, więc current zwiększa się o jeden. Zero go kończy, więc current wraca do 0. Po każdej jedynce porównaj current z best.

Dla [1, 1, 0, 1, 1, 1, 0, 1] current przyjmuje wartości 1, 2, 0, 1, 2, 3, 0, 1, a największa z nich to 3. Każdy ciąg jest mierzony na swoim ostatnim indeksie, gdzie current jest równy jego pełnej długości, więc najlepsza uzyskana wartość to długość najdłuższego ciągu.

Każda wartość jest odczytywana raz, co oznacza czas O(n), a do pamięci wystarczą dwie liczby całkowite.

Algorytm

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

Wersja z jednym przejściem jest krótka, więc błędy wynikają z tego, kiedy aktualizujesz wynik.

Aktualizowanie best tylko wtedy, gdy napotkasz 0. Seria, która dochodzi do końca tablicy, jak w przypadku [0, 1, 1], nigdy nie zostaje zapisana. Aktualizuj po każdej jedynce albo porównaj jeszcze raz po pętli.
Zapomnienie o zresetowaniu current po napotkaniu 0 sprawia, że jedynki z oddzielnych serii są sumowane, a dla [1, 1, 0, 1, 1] zwracana jest wartość 4.
Ustawienie początkowej wartości best na 1 lub na nums[0]. Tablica zawierająca same zera musi zwracać 0.
W Lua i R indeksowanie tablic zaczyna się od 1, więc podczas przechodzenia w przód sprawdzaj start + length ≤ n, a nie < n.

Najczęstsze pytania4

Jaka jest złożoność czasowa zadania „Maksymalna liczba kolejnych jedynek”?

Rozwiązanie przechodzące przez tablicę jeden raz działa w czasie O(n), ponieważ odczytuje każdą wartość dokładnie raz. Używa O(1) dodatkowej pamięci: jednego licznika bieżącej serii i jednego licznika najlepszego wyniku. Rozpoczynanie liczenia od nowa przy każdym indeksie zajmuje O(n²) czasu w przypadku tablicy składającej się wyłącznie z 1.

Dlaczego licznik resetuje się do 0 zamiast do 1?

Licznik przechowuje długość serii kończącej się na bieżącym indeksie. Gdy bieżąca wartość wynosi 0, nie kończy się tam żadna seria jedynek, więc jej długość wynosi 0. Następna jedynka zwiększa ją do 1, co jest prawidłową długością nowej serii.

Czy to problem z oknem przesuwnym?

Możesz potraktować to jako jedno: okno przechowuje bieżący ciąg, prawa krawędź przesuwa się przy każdej wartości, a 0 przesuwa lewą krawędź za siebie. Tutaj okno nigdy nie musi się zmniejszać krok po kroku, więc pojedynczy licznik zastępuje obie krawędzie. Widok z oknem przydaje się w trudniejszej wersji, w której możesz zamienić maksymalnie k zer na jedynki.

Jak policzyć kolejne jedynki, jeśli możesz zmienić jedno 0?

Prowadź dwa liczniki: długość ciągu kończącego się tutaj bez zmiany oraz długość ciągu, w którym wykorzystano już jedną zmianę. Przy 1 oba zwiększają się o jeden. Przy 0 licznik ciągu ze zmianą przyjmuje wartość zwykłego licznika plus jeden, a zwykły licznik resetuje się do 0. Odpowiedzią jest największa wartość licznika ciągu ze zmianą, jaką zobaczysz, nadal w jednym przebiegu.

Python

def findMaxConsecutiveOnes(nums):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane