Max Consecutive Ones
Du erhältst ein Array nums, in dem jeder Wert 0 oder 1 ist. Eine Folge ist eine Reihe von 1ern, die ohne eine 0 dazwischen direkt nebeneinander stehen. Gib die Länge der längsten Folge zurück oder 0, wenn das Array keine einzige 1 enthält.
Funktion
- numsinteger-array
- ein Array aus Nullen und Einsen
- Gibt zurückinteger
- die Länge der längsten Folge aufeinanderfolgender 1en
Einschränkungen
1 ≤ nums.length ≤ 2 × 104- Jedes
nums[i]ist0oder1.
Beispiele
- Eingabe
- nums = [1, 1, 0, 1, 1, 1, 0, 1]
- Ausgabe
- 3
- Erklärung
- Die 1er bilden drei Folgen: von Index
0bis1(Länge 2), von3bis5(Länge 3) und nur Index7(Länge 1). Die längste hat die Länge3.
- Eingabe
- nums = [0, 1, 0, 1, 1]
- Ausgabe
- 2
- Erklärung
- Die einzelne 1 am Index
1verliert gegen das Paar an den Indizes3und4, daher lautet die Antwort2.
- Eingabe
- nums = [0, 0, 0]
- Ausgabe
- 0
- Erklärung
- Es gibt nirgendwo eine 1, also gibt es keinen Lauf und die Antwort ist
0.
Weiterführende Frage
Was ist, wenn du bis zu k Nullen in Einsen umwandeln darfst? Wie lang kann die längste Folge werden, und kannst du sie immer noch in einem Durchlauf finden?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Eine Folge von Einsen endet, sobald eine
0erscheint. Was musst du dir über die Werte merken, an denen du bereits vorbeigekommen bist?Nur die Länge der Folge, die am aktuellen Index endet, ist relevant. Eine 1 verlängert sie um eins, und eine 0 setzt sie auf null zurück.
Durchlaufe das Array einmal mit zwei Zahlen: der Länge der aktuellen Folge und der bisher besten Länge. Erhöhe nach jeder 1 die aktuelle Folge und vergleiche sie mit der besten; setze nach jeder 0 die aktuelle Folge zurück.
Lösung
Ein Lauf endet in dem Moment, in dem eine 0 erscheint. Daher brauchst du an jedem Index nur die Länge des dort endenden Laufs. Ein Zähler, der bei einer 1 erhöht und bei einer 0 zurückgesetzt wird, findet den längsten Lauf in einem einzigen Durchgang.
Von jedem Index aus vorwärts zählen
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Probiere jeden Index als Startpunkt aus und gehe vorwärts, solange du 1en siehst; die Anzahl der Schritte entspricht der Länge des Laufs, der dort beginnt. Der längste Lauf beginnt an einem dieser Indizes, also ist die größte Anzahl die Antwort.
Die Durchläufe überschneiden sich. Bei einem Array aus n Einsen umfassen sie etwa n² / 2 Schritte, also 2 × 10^8 für n = 2 × 10^4.
Algorithmus
- Setze
best = 0. - Setze für jeden Index
startlength = 0. - Solange
start + lengthinnerhalb des Arrays liegt undnums[start + length]1ist, addiere 1 zulength. - Behalte den größeren Wert von
bestundlength. - Gib
bestzurü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 bestEin Durchlauf mit einem laufenden Zähler
Idee
Behalte current bei, die Länge der Folge von 1en, die am aktuellen Index endet. Eine 1 verlängert diese Folge um eins; eine 0 beendet sie, sodass current auf 0 sinkt. Jede Folge wird an ihrem letzten Index gemessen, an dem current ihrer gesamten Länge entspricht. Der größte Wert, den current erreicht, ist daher die Antwort.
Bei [1, 1, 0, 1, 1, 1, 0, 1] nimmt current die Werte 1, 2, 0, 1, 2, 3, 0, 1 an, und der größte Wert ist 3.
Algorithmus
- Setze
best = 0undcurrent = 0. - Für jeden Wert in
nums: Wenn er1ist, addiere 1 zucurrentund behalte den größeren Wert vonbestundcurrent. - Wenn er
0ist, setzecurrent = 0. - Gib
bestzurü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
bestnur zu aktualisieren, wenn du auf eine0triffst. Ein Lauf, der das Ende erreicht, wie bei[0, 1, 1], wird nie erfasst. Aktualisiere nach jeder1oder vergleiche nach der Schleife noch einmal.currentbei einer0nicht zurückzusetzen. Getrennte Läufe werden addiert, und[1, 1, 0, 1, 1]gibt4zurück.bestmit1oder mitnums[0]zu initialisieren.[0, 0, 0]muss0zurückgeben.- In Lua und R, wo Arrays bei 1 beginnen, den Vorwärtsdurchlauf mit
< nstatt≤ nzu begrenzen. Der letzte Wert wird nie gelesen, daher gibt[0, 1]0zurück.
Häufige Fragen3
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 einmal liest, und verwendet O(1) zusätzlichen Speicherplatz: einen Zähler für die aktuelle Folge und einen für die beste. Wird die Zählung an jedem Index neu gestartet, dauert das bei einem Array aus lauter 1en O(n²).
Warum wird der Zähler auf 0 statt auf 1 zurückgesetzt?
Der Zähler enthält die Länge des Laufs, der am aktuellen Index endet. Wenn der Wert dort 0 ist, endet dort kein Lauf aus 1en, also beträgt die Länge 0. Die nächste 1 erhöht ihn auf 1, die Länge des neuen Laufs.
Ist „Max Consecutive Ones“ ein Problem mit einem gleitenden Fenster?
Du kannst es als eine Einheit betrachten: Das Fenster enthält den aktuellen Lauf, sein rechter Rand rückt bei jedem Wert weiter, und eine 0 verschiebt den linken Rand über sie hinaus. Das Fenster schrumpft nie Schritt für Schritt, daher ersetzt ein Zähler die beiden Ränder.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def findMaxConsecutiveOnes(nums):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
nums = [1, 1, 0, 1, 1, 1, 0, 1]
Erwartete Ausgabe
3