Ich habe gerade ein Stack-basiertes Problem mit HackerRank versucht
Alexa hat zwei Stapel nichtnegativer Ganzzahlen, Stapel A und Stapel B, wobei Index 0 die Oberseite des Stapels angibt. Alexa fordert Nick heraus, das folgende Spiel zu spielen:
Bei jeder Bewegung kann Nick eine ganze Zahl von der Spitze eines der Stapel A oder B entfernen.
Nick behält eine laufende Summe der ganzen Zahlen bei, die er von den beiden Stapeln entfernt.
Nick wird vom Spiel disqualifiziert, wenn seine laufende Summe zu irgendeinem Zeitpunkt größer wird als eine zu Beginn des Spiels gegebene Ganzzahl X.
Nicks Endergebnis ist die Gesamtzahl der ganzen Zahlen, die er aus den beiden Stapeln entfernt hat.
finde die maximal mögliche Punktzahl, die Nick erreichen kann (d. h. die maximale Anzahl an ganzen Zahlen, die er entfernen kann, ohne disqualifiziert zu werden), während eines jeden Spiels und drucke es in einer neuen Zeile aus.
Drucken Sie für jedes der Spiele eine ganze Zahl in einer neuen Zeile, die die maximal mögliche Punktzahl angibt, die Nick erreichen kann, ohne disqualifiziert zu werden.
%Vor%Unten ist mein Code Ich habe den gierigen Ansatz versucht, indem ich das minimale Element von der Spitze des Stacks genommen habe & amp; addiere es zur Summe. Es funktioniert gut für einige der Testfälle, scheitert aber für den Rest wie für die folgende Eingabe
%Vor% Mein Code gibt 5 an, aber die richtige Lösung ist 6 Die Elemente, die in Serie herauskommen, sind 19,9,8,11,17,1
Die ersten drei Elemente von Stack A & amp; dann von Stack B.
**
Ich verstehe den Algorithmus nicht. Es erscheint mir wie DP für jemanden Hilf mir mit dem Ansatz / Algorithmus?
**
%Vor%Ok, ich werde versuchen, einen Algorithmus zu erklären, der dieses Problem im Grunde mit O (n) lösen kann, Sie müssen es selbst programmieren.
Ich werde es auf dem einfachen Beispiel erklären und Sie können es reflektieren
%Vor%Zuerst müssen Sie zwei Arrays erstellen, das Array enthält die Summe aller Zahlen bis zu seinem Index des Stapels, zum Beispiel für Stack A haben Sie dieses Array
%Vor%Das Gleiche gilt für Stack B
%Vor%Beginnen Sie dann für jedes Array mit dem Iterieren vom Ende des Arrays, bis Sie eine Zahl kleiner oder gleich der "Summe, die Sie nicht überschreiten sollten"
erreichenNun ist Ihre aktuelle Summe die Summe des Punktes, den Sie in beiden Arrays erreicht haben, sollte 10 +3 = 13 sein, um 10 zu erreichen, müssen Sie unbedingt mehr Einträge entfernen
Um die zusätzlichen Einträge zu entfernen, werden wir die Indizes erneut auf das Array verschieben, um zu entscheiden, welches Array den Index bewegen soll, den Eintrag, auf den Sie zeigen (10 für Array 1 und 3 für Array 2) und nach Index sortiert +1 (10/3 ~ 3), (3/2 ~ 1) verschieben Sie dann den Index für den höchsten Wert und berechnen Sie die Summe neu
Wenn beide Werte gleich sind, ist es logisch, den Index auf den Wert zu verschieben, der einen größeren Unterschied zu seinem vorherigen Wert hat (denken Sie daran, dass wir den Index in umgekehrter Reihenfolge verschieben).
Das Ergebnis ist die Summe der Indizes +2.
Diese Lösung funktioniert super .... ich hoffe es hilft ...
%Vor%Tags und Links algorithm java stack data-structures