Jump Game

+10

Du befindest dich am Index 0 des Arrays nums. Vom Index i aus kannst du beliebig viele Schritte nach vorne springen, von 1 bis zu nums[i]. Das bedeutet, nums[i] ist dein längster Sprung von dort, und bei 0 kannst du dich nicht bewegen. Gib true zurück, wenn eine Folge von Sprüngen den letzten Index erreicht, andernfalls false.

Funktion

canJump(nums: integer-array) → boolean

numsinteger-array: der weiteste Sprung, den du von jedem Index aus machen kannst
Gibt zurückboolean: true, wenn du vom Index 0 aus den letzten Index erreichen kannst, andernfalls false

Einschränkungen

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 10⁵
Ein Sprung kann kürzer sein als nums[i], sodass ein langer Sprung dich nie über den letzten Index hinaus zwingt.

Beispiele

Eingabe: nums = [2, 0, 3, 1, 0, 2]
Ausgabe: true
Erklärung: Von Index 0 aus erreichst du Index 1 oder 2. An Index 1 steht 0, und dort ist eine Sackgasse, aber an Index 2 steht 3, und von dort erreichst du Index 5, den letzten Index.

+18 versteckte Tests beim Einreichen

Weiterführende Frage

Zähle die verschiedenen Sprungfolgen, die auf dem letzten Index landen, modulo 10^9+7 und weiterhin in O(n)-Zeit.

Tipps

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

0 von 3 geöffnet

Lösung

Die Anzahl der möglichen Routen wächst exponentiell, daher kann es bei langen Arrays nicht funktionieren, die Routen einzeln zu prüfen. Entscheidend ist, dass die Indizes, die du erreichen kannst, immer einen zusammenhängenden Block bilden, der bei Index 0 beginnt. Eine Zahl, das rechte Ende dieses Blocks, enthält alles, was du brauchst, und ein einziger Durchlauf entscheidet über die Antwort.

Probiere jeden Sprung aus

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

Idee

Die direkteste Idee ist, es auszuprobieren. Stelle dich auf Index 0 und probiere nacheinander jede Landestelle aus, die dein Sprung zulässt. Wiederhole dasselbe von jeder Landestelle aus. Wenn ein Zweig auf dem letzten Index landet, lautet die Antwort true. Wenn jeder Zweig in einer Sackgasse endet, lautet sie false.

Im ersten Beispiel enthält Index 0 den Wert 2, also probierst du Index 1 und Index 2 aus. Index 1 enthält den Wert 0, eine Sackgasse. Daher gehst du zurück und probierst Index 2 aus. Index 2 enthält den Wert 3 und erreicht Index 5, den letzten Index, und die Suche endet mit true.

Die Suche ist korrekt, weil sie jede Route betrachtet. Das ist zugleich ihr Problem: Sie merkt sich nie einen Index, den sie bereits erkundet hat, und erkundet denselben Index deshalb erneut für jede Route, die ihn erreicht. Wenn die Antwort false lautet, muss sie jede Route ausschließen. In [4, 3, 2, 1, 0, 5] kann jeder Index vor der 0 die 0 erreichen, wodurch 8 verschiedene Routen dorthin führen. Bei 30 solchen Indizes gibt es mehr als 500 Millionen Routen, und die größten Tests umfassen 10,000 Elemente. Eine so lange Route führt in manchen Sprachen außerdem zum Überlauf des Aufrufstapels: Python stoppt standardmäßig nach 1,000 verschachtelten Aufrufen.

Algorithmus

Schreibe eine Hilfsfunktion reach(i), die beantwortet: Kannst du vom Index i zum letzten Index gelangen?
Wenn i der letzte Index ist, gib true zurück.
Andernfalls probiere alle möglichen Landepunkte next von i+1 bis min(i+nums[i], n-1) aus und gib true zurück, sobald reach(next) dies tut.
Wenn kein Landepunkt funktioniert, gib false zurück.
Die Antwort ist reach(0).

def canJump(nums):
    last = len(nums) - 1

    def reach(i):
        # Can you get from index i to the last index?
        if i == last:
            return True
        for nxt in range(i + 1, min(i + nums[i], last) + 1):
            if reach(nxt):
                return True
        return False

    return reach(0)

Merke dir, welche Indizes beendet werden können

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

Idee

Bei der obigen Suche wird immer wieder dieselbe Frage gestellt: „Kann der Index j das Ziel erreichen?“ Die Antwort für j ändert sich nie, also berechne sie einmal und speichere sie. Ein Index heißt gut, wenn man von dort aus den letzten Index erreichen kann. Der letzte Index ist gut. Jeder andere Index i ist gut, wenn mindestens einer der Indizes, die von i+1 bis i+nums[i] erreichbar sind, gut ist.

Jeder Index hängt nur von den Indizes rechts davon ab, also fülle eine Tabelle good von rechts nach links aus. Im ersten Beispiel ist Index 5 gut. An Index 4 steht 0, also ist er nicht gut. Von Index 3 aus ist nur Index 4 erreichbar: nicht gut. Von Index 2 aus sind die Indizes 3, 4 und 5 erreichbar, und 5 ist gut, also ist 2 gut. An Index 1 steht 0: nicht gut. Von Index 0 aus sind 1 und 2 erreichbar, und 2 ist gut, also lautet die Antwort true.

Über jeden Index wird jetzt einmal entschieden, aber bei dieser Entscheidung können immer noch bis zu n Zellen durchlaufen werden. In [9998, 9997, …, 1, 0, 7] kann jeder Index die 0 erreichen und nichts dahinter, also wird jeweils der gesamte Bereich durchsucht und nichts Gutes gefunden. Bei 10.000 Elementen sind das etwa 5 × 10^7 Prüfungen, und die größten Tests sind genau so aufgebaut. Der Aufwand wächst mit dem Quadrat der Länge, sodass der Algorithmus bei diesen Tests das Zeitlimit überschreitet.

Algorithmus

Erstelle ein boolesches Array good der Länge n und setze good[n-1] auf true.
Gehe i von n-2 bis hinunter zu 0 durch.
Durchsuche j von i+1 bis min(i+nums[i], n-1). Wenn irgendein good[j] true ist, setze good[i] auf true und beende die Suche.
Gib good[0] zurück.

def canJump(nums):
    n = len(nums)
    good = [False] * n  # good[i]: from i you can reach the last index
    good[n - 1] = True
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, min(i + nums[i], n - 1) + 1):
            if good[j]:
                good[i] = True
                break
    return good[0]

Verfolge den am weitesten erreichbaren Index

Idee

Achte darauf, welche Indizes du erreichen kannst, nicht auf die Routen. Vom Index i aus kannst du auf jedem Index von i+1 bis i+nums[i] landen, ohne Lücken. Sobald Index i erreichbar ist, ist also auch jeder Index bis i+nums[i] erreichbar. Beginne nur mit Index 0 und füge immer weitere Abschnitte hinzu. Jeder neue Abschnitt beginnt innerhalb des Blocks, den du bereits hast. Daher bilden die erreichbaren Indizes immer einen zusammenhängenden Block, [0, farthest].

Deshalb reicht eine einzige Zahl aus. Gehe i von links nach rechts durch. Solange i ≤ farthest gilt, ist Index i erreichbar. Vergrößere also farthest auf max(farthest, i+nums[i]). Falls i jemals größer als farthest wird, springt kein erreichbarer Index zu i. Der Block kann nicht über diese Lücke hinaus wachsen, daher ist nichts rechts davon erreichbar, auch nicht der letzte Index. Wenn du ohne Lücke das Ende erreichst, ist der letzte Index erreichbar.

Im zweiten Beispiel ist farthest zunächst 0, dann nach Index 0 gleich 1 und nach Index 1 gleich 4. An den Indizes 2, 3 und 4 steht 0, sodass der Wert bei 4 bleibt. Index 5 liegt hinter 4, also lautet die Antwort false. Im ersten Beispiel vergrößert Index 2 farthest auf 5, und kein Index liegt jemals dahinter. Daher lautet die Antwort true.

Warum ist es sicher, nur die größte Reichweite zu speichern? Du legst dich nie auf einen Sprung fest. Der Block enthält jeden Index, den irgendeine Route erreichen kann, und jede kürzere Landestelle liegt darin. Wenn du alles außer dem rechten Ende verwirfst, geht keine Information verloren.

Algorithmus

Setze farthest = 0.
Gehe jeden Index i von links nach rechts durch: Wenn i > farthest, gib false zurück.
Setze andernfalls farthest = max(farthest, i+nums[i]).
Wenn die Schleife beendet wird, war jeder Index erreichbar. Gib also true zurück.

def canJump(nums):
    farthest = 0  # every index up to farthest can be reached
    for i, jump in enumerate(nums):
        if i > farthest:
            return False  # nothing reachable jumps to i
        farthest = max(farthest, i + jump)
    return True

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen dadurch, dass man nums[i] als den einzigen Sprung versteht oder die Reihenfolge der beiden Prüfungen innerhalb der Schleife verwechselt.

Immer genau nums[i] Schritte zu springen oder immer den längsten Sprung zu wählen. Bei [2, 5, 0, 0] landet der volle Sprung von Index 0 auf einer 0, während der Sprung um 1 Schritt zu Index 1 das Ende erreicht.
false zurückzugeben, sobald man eine 0 sieht. Eine 0 ist nur dann relevant, wenn kein Sprung von einer vorherigen Position über sie hinwegführt: [2, 0, 1] überspringt die 0, und die Antwort ist true.
farthest zu aktualisieren, bevor man i > farthest prüft. Ein Index, den du nicht erreichen kannst, darf den Bereich nicht erweitern. Prüfe also zuerst und aktualisiere dann.
Ein Array mit einem Element als Fehlschlag zu behandeln. Du stehst bereits auf dem letzten Index, also ist die Antwort true, selbst wenn dieses Element 0 ist.
Bei langen Arrays Rekursion zu verwenden. Eine Route kann 10,000 Sprünge lang sein, wodurch in mehreren Sprachen der Aufrufstapel überläuft. Der einzelne Durchlauf kommt ohne Rekursion aus.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Jump Game?

Der Durchlauf mit der größten Reichweite besucht jeden Index einmal und läuft daher in O(n) Zeit mit O(1) zusätzlichem Speicherplatz. Der Tabellenansatz hat im schlimmsten Fall eine Laufzeit von O(n²), und alle Routen auszuprobieren ist exponentiell.

Warum funktioniert der Greedy-Ansatz für Jump Game?

Da auch kürzere Sprünge erlaubt sind, bedeutet das Erreichen von Index i, dass du jeden Index bis einschließlich i+nums[i] erreichen kannst. Diese Abschnitte überschneiden sich immer mit dem bereits erreichten Bereich, sodass die erreichbaren Indizes einen zusammenhängenden Block bilden, der bei 0 beginnt. Der Greedy-Durchlauf verfolgt nur das rechte Ende dieses Blocks, das den gesamten Block beschreibt, sodass er niemals einen Weg verwirft, der hätte funktionieren können.

Ist Jump Game ein Problem der dynamischen Programmierung?

Das lässt sich mit dynamischer Programmierung lösen: Markiere jeden Index als gut, wenn eines seiner möglichen Zielfelder gut ist, und fülle die Tabelle von rechts nach links. Das benötigt O(n²). Beachte, dass nur der am weitesten links liegende gute Index wichtig ist, da jeder Index, der einen guten Index erreicht, auch den am weitesten links liegenden erreicht. Behalte nur diesen Index, goal, und verschiebe ihn auf i, wenn i+nums[i] ≥ goal gilt. Die Antwort lautet, ob goal bei 0 endet – ein Durchlauf mit O(n), der dem gierigen Verfahren entspricht.

Wie findest du die minimale Anzahl an Sprüngen?

Verwende dieselbe Idee der größten Reichweite schichtweise. Behalte das Ende des Blocks im Blick, den du mit der aktuellen Anzahl an Sprüngen erreichen kannst, sowie den am weitesten entfernten Index, den der nächste Sprung erreichen kann. Wenn i das Ende des aktuellen Blocks überschreitet, brauchst du einen weiteren Sprung, und der nächste Block endet bei diesem am weitesten entfernten Index. Das ist weiterhin ein Durchlauf mit O(n).

Python

def canJump(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [2, 0, 3, 1, 0, 2]

Erwartet

true

Jump Game

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere jeden Sprung aus

Merke dir, welche Indizes beendet werden können

Verfolge den am weitesten erreichbaren Index

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben