0

我需要在螺旋阵列中添加枢轴点，如下所示：

 21 22 23 24 25 
 20   7   8   9 10
 19 6   1   2 11
 18   5   4   3 12
  17 16 15 14 13

我有 java 代码可以做到这一点，它适用于如上所示的小型 5x5 数组......但是当我用大型 1001x1001 数组测试它时，它给了我很多堆栈溢出。我不知道如何跟踪它，我已经使用 try and catch 没有成功。代码如下。有没有人有什么建议？

public class Spiral {
    int[][] arr = new int[1001][1001];
    int counter = 1;
    public int total = 1;
    String direction = "SOUTH";
    public Spiral(){
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                arr[i][j] = 0;
            }
        }
        try {
        arr[500][500] = 1;
        spiral(500, 501);
        total += arr[0][arr.length - 1];
        System.out.println(total);
        } catch (Exception e) {
            e.printStackTrace();
            //System.out.println(x + ", " + y);
        }
    }

    public void spiral(int x, int y) {

            counter++;
            arr[x][y] = counter;

            if(x==900&&y==900)
                System.out.println("here");
            if (direction == "SOUTH") {
                if (arr[x][y - 1] != 0) {
                    if (x + 1 < arr.length)
                    spiral(x + 1, y);
                } else {
                    total += arr[x][y];
                    direction = "WEST";
                    spiral(x, y - 1);
                }
            } else if (direction == "WEST") {
                if (arr[x - 1][y] != 0) {
                    if (y - 1 >= 0) {
                        spiral(x, y - 1);
                    }
                } else {
                    total += arr[x][y];
                    direction = "NORTH";
                    spiral(x - 1, y);
                }
            } else if (direction == "NORTH") {
                if (arr[x][y + 1] != 0) {
                    if (x - 1 >= 0) {
                        spiral(x - 1, y);
                    }
                } else {
                    total += arr[x][y];
                    direction = "EAST";
                    spiral(x, y + 1);
                }
            } else if (direction == "EAST") {
                if (arr[x + 1][y] != 0) {
                    if (y + 1 < arr.length) {
                        spiral(x, y + 1);
                    }
                } else {
                    total += arr[x][y - 1];
                    direction = "SOUTH";
                    spiral(x + 1, y);
                }
            }

    }
}
4

4 回答 4

4

螺旋（int，int）是递归的，并且多次调用自身以至于溢出堆栈。你有两个选择：

  1. 重构你的算法以循环而不是递归
  2. 使用 vm arg -Xss 增加堆栈大小。默认情况下，vm 使用 512 KB 作为堆栈，因此您可以尝试使用 -Xss1m 将该大小加倍（或您可能需要的任何其他值）
于 2012-07-10T16:58:57.647 回答
0

您的算法针对数组中的每个单元格重复出现。你的筹码真的足够大到可以重复 1,002,001 次吗？如果没有，那么您将不得不使您的堆栈更大或尝试不同的算法。

于 2012-07-10T16:58:03.733 回答
0

我会假设你看到这个问题是因为你的递归是如何工作的。您正在spiral递归调用以打印出您的数据，但是当使用 1001x1001 数据集调用它时，您正在创建一个同样大的堆栈跟踪，导致您的 JVM 崩溃并最终给您带来 Stack Overflow 错误。

于 2012-07-10T16:58:08.833 回答
0

由于您使用的是 recursion ，很明显您将获得大输入的 StackOverFlow 异常。

尝试使用 -Xss 开关调整 vm。

于 2012-07-10T17:05:06.433 回答