Ich möchte die Anzahl der Möglichkeiten finden, ein Array in 3 zusammenhängende Teile zu unterteilen, so dass die Summe der drei Teile gleich ist
%Vor%Mein Ansatz: Eingabe und Überprüfung für den Basisfall:
%Vor%Wenn die Antwort nicht darüber liegt Dann bilden Sie die Präfix- und Suffix-Summe.
%Vor%Suffix-Summe und Aktualisieren des binären Indexbaums:
%Vor%Und jetzt einfach Looping das Array, um die gesamten Wege zu finden: int ans = 0;
%Vor% Ich bekomme die falsche Antwort für den obigen Ansatz
Ich weiß nicht, wo ich Fehler gemacht habe Bitte helfen Sie, meinen Fehler zu korrigieren
Update- und Abfragefunktion:
Was Ihren Ansatz betrifft, ist es korrekt. Aber es gibt einige Punkte, wegen denen es WA geben könnte
Nachdem Sie gesagt haben, dass die Verwendung eines BIT-Baums hier ein Overkill ist, kann dies in O (n) im Vergleich zu Ihrer O (nlogn) -Lösung geschehen (tut es aber egal, wenn du dich bei einem Online-Richter einreichst).
Für den O (n) Ansatz nehmen Sie einfach Ihr Suffix [] Array. Und wie Sie getan haben, markieren Sie Suffix [i] = 1 wenn sum Von i bis n ist sum / 3 . Wenn Sie das Array rückwärts durchlaufen, können Sie dies in O (n) tun .
Dann traversiere einfach wieder rückwärts und mache suffix [i] + = suffix [i-1] (abgesehen vom Basisfall i = n). Nun speichert
Also, was ich vorschlagen, entweder schreiben Sie eine Bruteforce oder dieses einfache O (n) und überprüfen Sie Ihren Code dagegen,
Denn was Ihre Herangehensweise anbelangt, ist es korrekt und Debugging ist etwas, das nicht dafür geeignet ist
stackoverflow.
Zuerst berechnen wir ein Array dp , mit dp [i] = sum von 0 bis i, dies kann in O (n)
Zweitens, sagen wir, die Gesamtsumme des Arrays ist x, also müssen wir herausfinden, an welcher Position wir dp [i] == x / 3;
haben Für jede i-Position, die dp [i] == 2 * x / 3 hat, müssen wir zum Endergebnis die Zahl des Index j & lt; ich, die dp[j] == x/3 .
Die Antwort ist in result .
Was mit Ihrem Ansatz falsch ist, ist
%Vor%Das ist falsch, es sollte
sein %Vor%Weil wir nur die von 1 nach i entfernen müssen, nicht 1 nach i + 1.
Nicht nur das, dieser Teil:
%Vor% Sollte i <= n - 1;
Ähnlich sollte dieser Teil, for(int i=n ;i>=3;i--) , i >= 1
Und erster Teil:
%Vor%Sollte
sein %Vor%Eine Menge kleiner Fehler in Ihrem Code, die Sie erst mühsam einsetzen müssen, um zu debuggen, springen, um hier zu fragen, ist keine gute Idee.
In der gestellten Frage müssen wir drei zusammenhängende Teile in einem Array finden, deren Summe gleich ist. Ich werde die Schritte zusammen mit dem Code-Snippet erwähnen, das das Problem für Sie löst.
Die Sache, die wir hier machen, ist, das Array von Start bis Len (Array) -3 zu durchlaufen. Beim Auffinden der Summe, Summe / 3, sagen wir Index I, haben wir die erste Hälfte, die wir benötigen.
Nun, kümmern Sie sich nicht um die zweite Hälfte und fügen Sie der Lösungsvariablen (initialisiert auf Null) einen Wert gleich end [i + 2] hinzu. end [i + 2] sagt uns die Gesamtzahl der Möglichkeiten beginnend mit i + 2 bis zum Ende, um eine Summe zu erhalten, die der Summe / 3 für den dritten Teil entspricht.
Hier haben wir uns um den ersten und den dritten Teil gekümmert, wobei wir uns auch um den zweiten Teil gekümmert haben, der standardmäßig gleich sum / 3 sein wird. Unsere Lösungsvariable wird die endgültige Antwort auf das Problem sein.
Nachstehend finden Sie die Codefragmente zum besseren Verständnis des oben genannten Algorithmus :: -
Hier führen wir den Rückwärtsscan durch, um die Anzahl der Möglichkeiten zu speichern, um für jeden Index sum / 3 vom Ende zu erhalten.
%Vor%Sobald wir das End-Array haben, machen wir die Vorwärts-Schleife und erhalten unsere endgültige Lösung
%Vor%Lösung speichert die endgültige Antwort, d. h. die Anzahl der Möglichkeiten, das Array in drei zusammenhängende Teile mit gleicher Summe zu teilen.