php小编草莓带您探讨Java编程中的一个常见问题:当使用for循环时出现stackoverflow错误,但使用if块却不会产生错误。这种现象可能源于for循环的重复调用导致栈溢出,而if块则避免了这种情况。通过深入分析问题根源和Java内存管理机制,可以更好地理解并解决这一问题。
我正在解决 dsa 问题
我使用的语言是 java se
链接:https://www.codingninjas.com/studio/problems/ninja-s-training_3621003
我知道我的解决方案是正确的,但对于其中一个测试用例(我不知道测试用例是什么,因为它不显示测试用例),我遇到了 stackoverflow 错误,所以我只是用一些 if 语句替换了 for 循环,它已修复,我想知道为什么我首先遇到错误
c++ 中的相同解决方案(使用 for 循环)也没有错误,java 和 c++ 的堆栈空间工作方式是否不同?
这两种方法中的函数调用量保持相同,但其中一种方法给出了 stackoverflow 错误,这是没有意义的。所以调用次数不可能超过堆栈空间,如果有人能为我解决这个问题那就太好了
这是带有for循环的代码:
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; } }
这里是带有 if 块的代码:
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; } }
第一个解决方案使用额外的局部变量 k
和 cur
,它们在堆栈上为递归函数的每个执行上下文分配。这意味着您的堆栈增长速度比第二个解决方案要快一些。
是的,每种语言环境都有自己的限制来管理其堆栈。它们通常也允许更改堆栈的最大大小。请参阅 for Java 和 for C++。
请注意,您还可以避免 if
块并一次性处理这三种情况:
int mx = Math.max(rec(day - 1, prev % 3 + 1, points), rec(day - 1, (prev + 1) % 3 + 1, points));
如果将 points
存储为静态变量(就像 dp
一样)并且不将其作为参数传递给递归函数,则可以减少更多堆栈空间。
用于获取递归函数结果的堆栈由于测试中可能存在很大的输入数字 n
,分配给 int cur
会溢出。
https://www.php.cn/link/efc9ea3e0c2ed2c2481fe1252019266e
以上是当我使用 for 循环时出现 stackoverflow 错误,但如果使用 if 块完成相同的操作,则不会产生错误的详细内容。更多信息请关注PHP中文网其他相关文章!