Ich erhalte einen Stackoverflow-Fehler, wenn ich eine for-Schleife verwende, aber wenn dasselbe mit einem if-Block durchgeführt wird, wird der Fehler nicht erzeugt

Der PHP-Editor Strawberry führt Sie zu einem häufigen Problem in der Java-Programmierung: Bei Verwendung einer for-Schleife tritt ein Stackoverflow-Fehler auf, bei Verwendung eines if-Blocks tritt jedoch kein Fehler auf. Dieses Phänomen kann darauf zurückzuführen sein, dass wiederholte Aufrufe der for-Schleife einen Stapelüberlauf verursachen, und der if-Block vermeidet diese Situation. Dieses Problem kann durch eine eingehende Analyse der Grundursache des Problems und des Java-Speicherverwaltungsmechanismus besser verstanden und gelöst werden.

Frageninhalt

Ich löse ein DSA-Problem

Die Sprache, die ich verwende, ist Java SE

Link: https://www.codingninjas.com/studio/problems/ninja-s-training_3621003

Ich weiß, dass meine Lösung richtig ist, aber für einen der Testfälle (ich weiß nicht, was ein Testfall ist, weil er keine Testfälle anzeigt) habe ich einen Stackoverflow-Fehler erhalten, also habe ich einfach die for-Schleife durch eine if-Schleife ersetzt Aussagen, es wurde behoben, ich frage mich, warum ich den Fehler überhaupt bekommen habe

Die gleiche Lösung in C++ (mit for-Schleife) funktioniert auch ohne Fehler. Funktioniert der Stapelspeicher in Java und C++ unterschiedlich?

Die Anzahl der Funktionsaufrufe in beiden Methoden bleibt gleich, aber eine der Methoden gibt einen Stackoverflow-Fehler aus, der keinen Sinn ergibt. Damit die Anzahl der Aufrufe den Stack-Speicherplatz nicht überschreiten darf, wäre es toll, wenn jemand dieses Problem für mich lösen könnte

Dies ist der Code mit der for-Schleife:

public class solution {
    private static int dp[][];
    private static int rec(int day, int prev, int[][] points) {
        if (day == 0) {
            // no more days left.
            return 0;
        }

        if (dp[day][prev] != -1) {
            return dp[day][prev];
        }

        // merit points of ith task on nth day.
        int ans = points[day - 1][prev - 1];
        int mx = 0;
        for(int k=1;k<4;k++)
        {
            if(k!=prev)
            {
                int cur=rec(day-1, k, points);
                mx=math.max(cur,mx);
            }
        }
        

        dp[day][prev] = ans + mx;
        return ans + mx;
    }

    public static int ninjatraining(int n, int points[][]) {
        // dp table to memoize the solution.
        dp = new int[n + 1][4];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 4; j++) {
                dp[i][j] = -1;
            }
        }
        int ans = 0;
        ans = math.max(ans, rec(n, 1, points));
        ans = math.max(ans, rec(n, 2, points));
        ans = math.max(ans, rec(n, 3, points));

        return ans;
    }
}

Hier ist der Code mit dem if-Block:

public class Solution {
    private static int dp[][];
    private static int rec(int day, int prev, int[][] points) {
        if (day == 0) {
            // No more days left.
            return 0;
        }

        if (dp[day][prev] != -1) {
            return dp[day][prev];
        }

        // Merit points of ith task on nth day.
        int ans = points[day - 1][prev - 1];
        int mx = 0;
        
        if (prev == 1) {
            mx = Math.max(rec(day - 1, 2, points), rec(day - 1, 3, points));
        }

        if (prev == 2) {
            mx = Math.max(rec(day - 1, 1, points), rec(day - 1, 3, points));
        }

        if (prev == 3) {
            mx = Math.max(rec(day - 1, 1, points), rec(day - 1, 2, points));
        }

        dp[day][prev] = ans + mx;
        return ans + mx;
    }

    public static int ninjaTraining(int n, int points[][]) {
        // DP table to memoize the solution.
        dp = new int[n + 1][4];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 4; j++) {
                dp[i][j] = -1;
            }
        }
        int ans = 0;
        ans = Math.max(ans, rec(n, 1, points));
        ans = Math.max(ans, rec(n, 2, points));
        ans = Math.max(ans, rec(n, 3, points));

        return ans;
    }
}

Lösung

Die erste Lösung verwendet zusätzliche lokale Variablen k 和 cur, die für jeden Ausführungskontext der rekursiven Funktion auf dem Stapel zugewiesen werden. Das bedeutet, dass Ihr Stack etwas schneller wächst als bei der zweiten Lösung.

Ja, jedes Gebietsschema hat seine eigenen Einschränkungen für die Verwaltung seines Stapels. Sie ermöglichen in der Regel auch die Änderung der maximalen Größe des Stapels. Siehe für Java und für C++.

Beachten Sie, dass Sie den if-Block auch vermeiden und alle drei Fälle gleichzeitig bearbeiten können:

int mx = Math.max(rec(day - 1, prev % 3 + 1, points), 
                  rec(day - 1, (prev + 1) % 3 + 1, points));

Sie können mehr Stapelplatz sparen, wenn Sie points als statische Variable speichern (genau wie dp) und sie nicht als Parameter an die rekursive Funktion übergeben. points 存储为静态变量（就像 dp 一样）并且不将其作为参数传递给递归函数，则可以减少更多堆栈空间。

用于获取递归函数结果的堆栈由于测试中可能存在很大的输入数字 n，分配给 int cur

Stack zum Erhalten rekursiver Funktionsergebnisse Aufgrund der möglichen großen Eingabezahlen n im Test kommt es bei der Zuweisung zu int cur zu einem Überlauf.

https://www.php.cn/link/efc9ea3e0c2ed2c2481fe1252019266e

🎜

Das obige ist der detaillierte Inhalt vonIch erhalte einen Stackoverflow-Fehler, wenn ich eine for-Schleife verwende, aber wenn dasselbe mit einem if-Block durchgeführt wird, wird der Fehler nicht erzeugt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!