Frage
Gegeben ein Array von ganzen Zahlen, wobei jedes Element die maximale Anzahl von Schritten darstellt, die von diesem Element vorwärts ausgeführt werden können. Schreibe eine Funktion, um die minimale Anzahl von Sprüngen zu erreichen, die erreicht werden sollen Ende des Arrays (beginnend mit dem ersten Element). Wenn ein Element ist 0, kann sich dann nicht durch dieses Element bewegen.
Beispiel
Eingabe: arr [] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Ausgabe: 3 (1- & gt; 3 - & gt; 8 - & gt; 9)
Mehrere Wege gefunden von Dynamic Programming approach zu anderen linearen Ansätzen. Ich bin nicht in der Lage, den linearen Ansatz zu verstehen. HIER ist der Link, wo ein linearer Ansatz vorgeschlagen wird.
Ich kann es überhaupt nicht verstehen. Was ich verstehen könnte, ist, dass der Autor vorschlägt, einen gierigen Ansatz zu machen und zu sehen, ob wir das Ende erreichen. Wenn nicht, dann zurückverfolgen?
Die Zeitkomplexität der auf der Site vorgeschlagenen Lösung ist linear, da Sie das Array nur einmal durchlaufen. Der Algorithmus vermeidet die innere Iteration meiner vorgeschlagenen Lösung mit einigen cleveren Tricks.
Die Variable maxReach speichert zu jeder Zeit die maximal erreichbare Position im Array. jump speichert die Anzahl der Sprünge, die notwendig sind, um diese Position zu erreichen. step speichert die Anzahl der Schritte, die wir noch ausführen können (und wird mit der Anzahl der Schritte an der ersten Array-Position initialisiert)
Während der Iteration werden die obigen Werte wie folgt aktualisiert:
Zuerst testen wir, ob wir das Ende des Arrays erreicht haben. In diesem Fall müssen wir nur die Variable jump zurückgeben.
Als nächstes aktualisieren wir die maximal erreichbare Position. Dies entspricht dem Maximum von maxReach und i+A[i] (die Anzahl der Schritte, die wir von der aktuellen Position ausführen können).
Wir haben einen Schritt gebraucht, um zum aktuellen Index zu kommen, also muss steps verringert werden.
Wenn keine weiteren Schritte übrig sind (zB steps=0 , dann müssen wir einen Sprung verwendet haben. Daher jump erhöhen. Da wir wissen, dass es irgendwie möglich ist, maxReach zu erreichen, initialisieren wir die Schritte auf den Betrag der Schritte, um maxReach von Position i zu erreichen.
Beispiel:
%Vor% Mein suboptimaler Algorithmus, der in O(nk) time mit n die Anzahl der Elemente im Array und k das größte Element im Array arbeitet und eine interne Schleife über array[i] verwendet. Diese Schleife wird durch den folgenden Algorithmus vermieden.
Code
%Vor% Hier ist eine andere lineare Lösung. Der Code ist länger als der in der Leet-Code-Link vorgeschlagene, aber ich denke, es ist einfacher zu verstehen. Es basiert auf zwei Beobachtungen: Die Anzahl der Schritte, die erforderlich sind, um die Position i + 1 zu erreichen, ist nie kleiner als die Anzahl der erforderlichen Schritte zum Erreichen der Position i und jedes Element weist seinen Wert +1 zu i + 1 ... i + a[i] zu Segment.
Komplexitätsanalyse:
Die Gesamtzahl der Elemente in toDelete lists ist O(n) . Dies ist der Fall, weil an jeder Position i höchstens ein Element hinzugefügt wird. Aus diesem Grund benötigt die Verarbeitung aller Elemente in allen toDelete -Listen lineare Zeit.
Der Wert min kann nur erhöht werden. Deshalb macht die innere while -Schleife höchstens n Iterationen insgesamt.
Die äußere for Schleife macht offensichtlich n Iterationen. Daher ist die zeitliche Komplexität linear.
Jahre zu spät zur Party, aber hier ist eine andere O (n) Lösung, die für mich Sinn ergab.
%Vor%Hier ist die grundlegende Intuition bezüglich des gierigen Ansatzes des oben genannten Problems und Ruhe sind die Code-Anforderungen.
Gegebenes Array ist Input: a [] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}.
Wir beginnen nun mit dem ersten Element, dh i = 0 und a [i] = 1. Wenn wir das sehen, können wir höchstens einen Sprung der Größe 1 machen, und da wir keine andere Wahl haben, machen wir das Schritt geschehen.
Momentan sind wir bei i = 1 und a [i] = 3. Daher können wir momentan einen Sprung der Größe 3 machen, aber wir betrachten stattdessen alle möglichen Sprünge, die wir vom aktuellen Ort aus machen können, und erreichen den maximalen Abstand, der innerhalb der Grenzen (des Arrays) liegt. Also, was sind unsere Entscheidungen? wir können einen Sprung von 1 Schritt oder 2 Schritten oder 3 Schritten machen. Also untersuchen wir vom aktuellen Standort aus für jede Größe Sprünge und wählen diejenige aus, die uns maximal weiter in das Array bringen kann.
Sobald wir entschieden haben, an welchem Punkt wir bleiben sollen, nehmen wir diese Sprunggröße und aktualisieren unsere Anzahl der bisherigen Sprünge und auch die, wo wir maximal erreichen können und wie viele Schritte wir jetzt haben, um unseren nächsten Zug zu entscheiden. Und das ist es. So wählen wir schließlich die beste Option aus, die das Array linear durchquert. Das ist also die Grundidee des Algo, nach dem Sie suchen. Als nächstes müssen Sie den Algorithmus so programmieren, dass er funktioniert. Prost!
Hoffe, dass jemand Zeit reist und die Intuition hilfreich findet !! :): P "Jahre zu spät zur Party" @Vasilescu Andrei - gut gesagt. Manchmal empfinde ich es als Zeitreisende.