Enhanced FrogRiverN

Question

Ich arbeite ein paar Programmierübungen. Dieser ist an verschiedenen Stellen recht bekannt und beantwortet worden.

FrogRiverOne Finden Sie die früheste Zeit, wenn ein Frosch auf die andere Seite eines Flusses springen kann. https://codility.com/programmers/task/frog_river_one/

Meine Frage ist, was ist, wenn der Frosch eine Entfernung von D springen kann? Wie finden wir die kürzeste Zeit, um den Fluss zu überqueren, mit der besten Laufzeit Komplexität? Vielen Dank!

int solution(int X, vector<int> &A, int D); // frog can jumps from 1 to D steps 

Answer 1

Ich denke shole gierige Lösung fast richtig ist. Wenn Sie einen rekursiven Fortpflanzungsschritt beim Ändern von Current_Pos einfügen, stellen Sie sicher, dass sich der Strahl immer in der vordersten Position befindet. Hier

ist eine Alternative, die die Rekursion vermeidet:

Verwenden eines Belegungs Array, dass Geschäfte für jede Position, wenn ein Blatt ist. Und verwenden Sie eine union-find Datenstruktur mit Knoten für jede Position. Die Vereinigungsfindungs-Datenstruktur verfolgt Knoten, die voneinander erreichbar sind (d. H. Verbundene Komponenten). Die Aufgabe besteht dann darin, den ersten Zeitpunkt zu finden, an dem beide Ufer miteinander verbunden sind.

Um dies zu finden, gehen Sie folgendermaßen vor: Jedes Mal, wenn ein neues Blatt ins Spiel kommt, markieren Sie seine Position als besetzt. Vereinigen Sie dann den Knoten in der Union-Find-Datenstruktur mit jedem anderen belegten Knoten, der von dieser Position aus erreichbar ist (-D bis +D). Überprüfen Sie abschließend, ob beide Ufer miteinander verbunden sind. Die gesamte Zeitkomplexität ist O(ND+X).

Welche der beiden Lösungen schneller ist, hängt von der Eingabe ab.