So finden Sie die minimale Anzahl der Sprünge bis zum Ende des Arrays in O(n) Zeit
Frage
Gegeben sei ein Integer-array wo jedes element steht für die maximale Anzahl der Schritte, die gemacht werden können nach vorne aus, dass element.
Schreiben Sie eine Funktion geben Sie die minimale Anzahl der Sprünge zu erreichen
Ende das array (beginnend mit dem ersten element). Wenn ein element ist
0, dann nicht bewegen Sie sich durch das element aus.Beispiel
Eingang: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Ausgabe: 3 (1-> 3 -> 8 ->9)
Fand mehrere Möglichkeiten, von Dynamische Programmierung Ansatz zu anderen linearen Ansätze. Ich bin nicht in der Lage zu verstehen, der Ansatz, von dem gesagt wird, linear in der Zeit. HIER ist der link, wo ein linearer Ansatz vorgeschlagen.
Ich bin nicht in der Lage zu verstehen, es überhaupt nicht. Was ich verstehen könnte ist, dass der Autor suggeriert, zu tun, ein greedy-Ansatz und sehen, ob wir erreichen Ende .. wenn nicht, dann backtrack ?
Du musst angemeldet sein, um einen Kommentar abzugeben.
Die Zeit, die Komplexität der vorgeschlagenen Lösung auf der Website ist linear, weil Sie nur die Iteration über das array einmal. Der Algorithmus vermeidet die innere iteration von meiner vorgeschlagenen Lösung mit einigen cleveren tricks.
Die variable
maxReach
speichert zu jeder Zeit die maximal zu erreichende position im array.jump
speichert die Höhe der Sprünge notwendig, um zu erreichen, dass die position.step
speichert die Anzahl der Schritte können wir immer noch (und ist entsprechend mit der Höhe der Stufen an der ersten array-position)Während der iteration, die oben genannten Werte sind wie folgt aktualisiert:
Zuerst testen wir, ob wir erreicht haben, am Ende des Arrays, in welchem Fall wir nur zurückgeben müssen
jump
variable.Nächstes aktualisieren wir die maximal zu erreichende position. Dies entspricht der maximal
maxReach
undi+A[i]
(die Anzahl der Schritte, die wir ergreifen können, von der aktuellen position).Wir einen Schritt, um den aktuellen index, also
steps
verkleinert werden.Wenn keine weiteren Schritte übrig sind (d.h.
steps=0
ist, dann müssen wir verwendet haben, einen Sprung. Daher erhöhenjump
. Da wir wissen, dass es irgendwie möglich ist das zu erreichenmaxReach
wir initialisieren die Schritte, um die Anzahl von Schritten zu erreichenmaxReach
von der positioni
.Beispiel:
Meiner suboptimalen Algorithmus, der arbeitet in
O(nk)
Zeit mitn
die Anzahl der Elemente im array undk
das größte element im array und verwendet eine interne Schleife überarray[i]
. Diese Schleife wird vermieden, indem die unten Algorithmus.Code
jump
nie versagt (Beispiel:A[] = {0,1}
undA[]={1,3,1,0,0,0,0,1}
, ausfallen sollte, laut Beschreibung der Frage). sollten Sie nicht fügen Sie eine Bedingung am Anfang der Schleife:if (steps == 0) return INT_MAX;
, und ein return am Ende der Funktion (obwohl Sie sollten nie dort):return INT_MAX;
?, thnx!Jahre zu spät zur party , aber hier ist noch O(n) Lösung, die Sinn machte für mich.
Hier ist eine lineare Lösung. Der code ist länger als die, die vorgeschlagen, in der leet-code-link, aber ich glaube, es ist einfacher zu verstehen. Es basiert auf zwei Beobachtungen: die Anzahl der Schritte, die zum erreichen der
i + 1
position ist nie kleiner als die Anzahl der Schritte, die zum erreichen deri
position und jedes element, jedes element weist dessen Wert + 1 zui + 1 ... i + a[i]
segment.Komplexität-Analyse:
Kann die Gesamtanzahl der Elemente in
toDelete
Listen istO(n)
. Es ist der Fall, da an jeder positioni
höchstens ein element Hinzugefügt wird. Das ist, warum die Verarbeitung aller Elemente in allentoDelete
Listen erfordert lineare Zeit.Den
min
Wert kann nur erhöht werden. Das ist, warum die innerewhile
Schleife macht bei den meistenn
Iterationen insgesamt.Den äußeren
for
Schleife offensichtlich machtn
Iterationen. So, die Zeit-Komplexität ist linear.dp[i] <= dp[i + 1]
für allei
.Hier ist die grundlegende intuition in Bezug auf das obige problem ist greedy-Ansatz und der rest sind die Anforderungen des Kodex.
Gegeben array Input: [] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}.
Nun starten wir ab dem 1. element ich.e i=0 und a[i] = 1. So sieht dies können wir höchstens einen Sprung der Größe 1, also da haben wir keine andere Wahl, also machen wir diesen Schritt passieren.
Derzeit sind wir bei i=1 und a[i]=3. So haben wir derzeit einen Sprung machen kann der Größe 3, aber stattdessen betrachten wir alle möglichen Sprünge können wir von der aktuellen Lage und erreichen die maximale Entfernung, die innerhalb der Grenzen(des Arrays). Also, was sind unsere Möglichkeiten? wir machen einen Sprung von Schritt 1 oder 2 Schritte oder 3 Schritte. So untersuchen wir die von der aktuellen Position für jede Größe Sprünge und wählen Sie diejenige, die können uns höchstens weiter in das array.
Einmal haben wir uns entschieden, denen wir bleiben, die wir nehmen, die den Sprung von Größe und aktualisieren die Anzahl der Sprünge, die bisher und auch denen, die wir erreichen können und wie viele Schritte haben wir jetzt zu entscheiden, unsere nächsten zu bewegen. Und das ist es. Dies ist, wie wir schließlich, wählen Sie die beste option Linear Durchlaufen des Arrays.
Das ist also die grundlegende Idee, die der algo vielleicht suchen Sie für die, als Nächstes den code für den Algorithmus zu arbeiten. Prost!
Hoffe, jemand Zeit reist und findet die intuition hilfreich!!!! 🙂 😛
"Jahre zu spät zur party" @Vasilescu, Andrej - gut gesagt. Manchmal fühlt es sich für mich, dass wir Zeitreisende.
Einfaches python-code für die Minimale Anzahl der Sprünge zu erreichen, Ende problem.