Max Consecutive Ones

Q: Wie hoch ist die Zeitkomplexität von „Max Consecutive Ones“?

Die Lösung mit einem Durchlauf benötigt O(n) Zeit, da sie jeden Wert genau einmal liest. Sie verwendet O(1) zusätzlichen Speicherplatz: einen Zähler für die aktuelle Folge und einen für die längste. Wird der Zähler an jedem Index neu gestartet, benötigt das bei einem Array, das nur aus 1en besteht, O(n²) Zeit.

Q: Warum wird der Zähler auf 0 statt auf 1 zurückgesetzt?

Der Zähler enthält die Länge der Folge, die am aktuellen Index endet. Wenn der aktuelle Wert 0 ist, endet dort keine Folge von 1en, also beträgt ihre Länge 0 . Die nächste 1 erhöht den Zähler dann auf 1 , die korrekte Länge einer neuen Folge.

Q: Ist das ein Sliding-Window-Problem?

Du kannst es als ein Fenster betrachten: Das Fenster enthält den aktuellen Durchlauf, der rechte Rand rückt bei jedem Wert weiter, und eine 0 verschiebt den linken Rand über sie hinaus. Hier muss das Fenster nie schrittweise verkleinert werden, sodass ein einzelner Zähler die beiden Ränder ersetzt. Die Fenstersicht lohnt sich bei der schwierigeren Variante, in der du bis zu k Nullen in Einsen umwandeln darfst.

Q: Wie zählt man aufeinanderfolgende 1en, wenn man eine 0 umdrehen darf?

Führe zwei Zähler: die Länge des Laufs, der hier ohne Wechsel endet, und die Länge mit einem bereits verwendeten Wechsel. Bei einer 1 erhöhen sich beide um eins. Bei einer 0 wird der Zähler mit Wechsel zum einfachen Zähler plus eins, und der einfache Zähler wird auf 0 zurückgesetzt. Die Antwort ist der größte Zähler mit Wechsel, den du siehst, weiterhin in einem Durchlauf.

EinsteigerArrays und Strings

+10

Du erhältst ein Array nums, in dem jeder Wert entweder 0 oder 1 ist. Eine Folge ist eine Reihe von Einsen, die ohne dazwischenliegende 0 direkt nebeneinander stehen. Gib die Länge der längsten Folge zurück oder 0, wenn das Array keine einzige 1 enthält.

Funktion

findMaxConsecutiveOnes(nums: integer-array) → integer

numsinteger-array: ein Array aus Nullen und Einsen
Gibt zurückinteger: die Länge des längsten Laufs aufeinanderfolgender 1en

Einschränkungen

1 ≤ nums.length ≤ 2 × 10⁴
Jedes nums[i] ist 0 oder 1.

Beispiele

Eingabe: nums = [1, 1, 0, 1, 1, 1, 0, 1]
Ausgabe: 3
Erklärung: Die 1er bilden drei zusammenhängende Abschnitte: die Indizes 0 bis 1 (Länge 2), 3 bis 5 (Länge 3) und den einzelnen Index 7 (Länge 1). Der längste Abschnitt hat die Länge 3.

Eingabe: nums = [0, 1, 0, 1, 1]
Ausgabe: 2
Erklärung: Die Läufe sind die einzelne 1 am Index 1 und das Paar an den Indizes 3 und 4. Das Paar gewinnt mit der Länge 2.

Eingabe: nums = [0, 0, 0]
Ausgabe: 0
Erklärung: Es gibt nirgendwo eine 1, also gibt es keine zusammenhängende Folge und die Antwort ist 0.

+14 versteckte Tests beim Einreichen

Weiterführende Frage

Was, wenn du bis zu k Nullen in Einsen umwandeln darfst? Wie lang kann die längste Folge von Einsen werden, und kannst du sie immer noch in einem Durchgang finden?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Ein Lauf endet in dem Moment, in dem eine 0 erscheint. Daher musst du an jedem Index nur wissen, wie lang der dort endende Lauf ist. An jedem Index von vorne zu zählen, wiederholt immer wieder dieselbe Arbeit. Ein Zähler, der bei einer 1 erhöht und bei einer 0 zurückgesetzt wird, beantwortet die Frage in einem einzigen Durchlauf.

Von jedem Index aus vorwärts zählen

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Jeder Lauf beginnt irgendwo. Probiere also jeden Index als Startpunkt aus und gehe weiter, solange du auf 1en triffst; die Anzahl der Schritte ist die Länge des Laufs, der dort beginnt. Die größte Anzahl über alle Startpunkte ist die Antwort. Bei [1, 1, 0, 1, 1, 1, 0, 1] geht der Start bei Index 3 über drei 1en, bevor er bei Index 6 auf die 0 trifft. Das ergibt 3.

Die Antwort ist korrekt, weil der längste Lauf an einem der Indizes beginnt, die du ausprobierst, und der Durchlauf von seinem ersten Index aus seine Länge genau misst.

Die Kosten stecken in den Überschneidungen. In einem Array mit n Einsen durchläuft der Start bei Index 0 n Schritte, der nächste n-1 und so weiter, insgesamt etwa n² / 2 Schritte. Für n = 2 × 10^4 sind das 2 × 10^8 Schritte – zu viele für das Zeitlimit in langsameren Sprachen.

Algorithmus

Setze best = 0.
Setze für jeden Index start length = 0.
Solange start + length innerhalb des Arrays liegt und nums[start + length] 1 ist, addiere 1 zu length.
Behalte den größeren Wert von best und length.
Gib best zurück.

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

Ein Durchlauf mit laufender Zählung

Idee

Durchlaufe das Array einmal und speichere current, die Länge der Folge von Einsen, die am aktuellen Index endet. Eine 1 verlängert diese Folge, also wird current um eins erhöht. Eine 0 beendet sie, also wird current wieder auf 0 gesetzt. Vergleiche nach jeder 1 current mit best.

Bei [1, 1, 0, 1, 1, 1, 0, 1] nimmt current die Werte 1, 2, 0, 1, 2, 3, 0, 1 an; der größte davon ist 3. Jede Folge wird an ihrem letzten Index gemessen, wo current ihrer vollen Länge entspricht. Daher ist der beste bisher gesehene Wert die längste Folge.

Jeder Wert wird einmal gelesen, was einer Laufzeit von O(n) entspricht. Zwei Ganzzahlen sind der gesamte benötigte Speicher.

Algorithmus

Setze best = 0 und current = 0.
Für jeden Wert in nums: Wenn er 1 ist, addiere 1 zu current und behalte den größeren Wert von best und current.
Wenn er 0 ist, setze current = 0.
Gib best zurück.

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

Stolperfallen und Grenzfälle

Die Version mit einem Durchlauf ist kurz, daher entstehen die Fehler an den Stellen, an denen du die Antwort aktualisierst.

best nur dann aktualisieren, wenn du auf eine 0 triffst. Ein Lauf, der wie bei [0, 1, 1] bis zum Ende des Arrays reicht, wird nie erfasst. Aktualisiere nach jeder 1 oder vergleiche nach der Schleife noch einmal.
Vergessen, current bei einer 0 zurückzusetzen. Dadurch werden die Einsen getrennter Läufe zusammengezählt und für [1, 1, 0, 1, 1] wird 4 zurückgegeben.
best auf 1 oder auf nums[0] setzen. Ein Array, das nur aus Nullen besteht, muss 0 zurückgeben.
In Lua und R beginnt das Array beim Index 1. Daher prüft der Vorwärtsdurchlauf start + length ≤ n statt < n.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von „Max Consecutive Ones“?

Die Lösung mit einem Durchlauf benötigt O(n) Zeit, da sie jeden Wert genau einmal liest. Sie verwendet O(1) zusätzlichen Speicherplatz: einen Zähler für die aktuelle Folge und einen für die längste. Wird der Zähler an jedem Index neu gestartet, benötigt das bei einem Array, das nur aus 1en besteht, O(n²) Zeit.

Warum wird der Zähler auf 0 statt auf 1 zurückgesetzt?

Der Zähler enthält die Länge der Folge, die am aktuellen Index endet. Wenn der aktuelle Wert 0 ist, endet dort keine Folge von 1en, also beträgt ihre Länge 0. Die nächste 1 erhöht den Zähler dann auf 1, die korrekte Länge einer neuen Folge.

Ist das ein Sliding-Window-Problem?

Du kannst es als ein Fenster betrachten: Das Fenster enthält den aktuellen Durchlauf, der rechte Rand rückt bei jedem Wert weiter, und eine 0 verschiebt den linken Rand über sie hinaus. Hier muss das Fenster nie schrittweise verkleinert werden, sodass ein einzelner Zähler die beiden Ränder ersetzt. Die Fenstersicht lohnt sich bei der schwierigeren Variante, in der du bis zu k Nullen in Einsen umwandeln darfst.

Wie zählt man aufeinanderfolgende 1en, wenn man eine 0 umdrehen darf?

Führe zwei Zähler: die Länge des Laufs, der hier ohne Wechsel endet, und die Länge mit einem bereits verwendeten Wechsel. Bei einer 1 erhöhen sich beide um eins. Bei einer 0 wird der Zähler mit Wechsel zum einfachen Zähler plus eins, und der einfache Zähler wird auf 0 zurückgesetzt. Die Antwort ist der größte Zähler mit Wechsel, den du siehst, weiterhin in einem Durchlauf.

Python

def findMaxConsecutiveOnes(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet