Java 中自调用函数中的堆栈溢出错误（岛数）

Question

我对导致堆栈溢出错误的原因进行了一些研究，我可以得出结论，它是由程序中的递归函数引起的，该函数应该“计算数组中的岛数”。我明白是什么导致了这个问题，但不确定为什么会发生这种情况，或者我的主要问题是实际该怎么做。我发现如果我通过让程序反复向控制台打印一些东西来减慢程序的速度，它可以工作，但需要很长时间才能完成。有没有办法可以保持程序速度而不会出错，或者有更好的方法来解决问题（搜索“岛数”以找到问题）。此外，该数组是二维的，大小为 1050 x 800。public class NumOfIslands {  static boolean[][] dotMap = new boolean[1050][800];  static boolean visited[][] = new boolean[1050][800];  static int total = 0;  public static void main(String args[]) {    defineArrays();    run();  }  public static void findObjects(int xCord, int yCord) {    for(int y = yCord - 1; y <= yCord + 1; y++) {      for(int x = xCord - 1; x <= xCord + 1; x++) {        if(x > -1 && y > -1 && x < dotMap[0].length && y < dotMap.length) {          if((x != xCord || y != yCord) && dotMap[x][y] == true && visited[x][y] != true) {            visited[x][y] = true;            findObjects(x,y);            //System.out.println("test");          }        }      }    }  }  public static void defineArrays() {    for(int y = 0; y < 800; y++) {      for(int x = 0; x < 1050; x++) {        dotMap[x][y] = true;      }    }  }  public static int run() {    //dotMap = DisplayImage.isYellow;    System.out.println(dotMap.length + " " + dotMap[0].length);    int objects = 0;    for(int y = 439; y < 560/*dotMap[0].length*/; y++) {      for(int x = 70; x < 300/*dotMap.length*/; x++) {        if(dotMap[x][y] == true && visited[x][y] != true) {          visited[x][y] = true;          objects++;          findObjects(x,y);        }      }    }    System.out.println("total" + total);    System.out.println(objects);    return objects;  }}

Answer 1

在您的示例中，每次调用都会findObjects从循环中将 2 个变量添加到堆栈 int x 和 int y。

最快的解决方案之一：

class Solution {

    int m, n;

    public int numIslands(char[][] grid) {

        if (grid == null || grid.length == 0) {

            return 0;

        }

        m = grid.length;

        n = grid[0].length;

        int counter = 0;

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (grid[i][j] == '1') {

                    visit(grid, i, j);

                    counter++;

                }

            }

        }

        return counter;

    }

    public void visit(char[][] grid, int i, int j) {

        if (i < 0 || i >= m || j < 0 || j >= n) {

            return;

        }

        if (grid[i][j] == '0') {

            return;

        }

        grid[i][j] = '0';

        visit(grid, i - 1, j);

        visit(grid, i + 1, j);

        visit(grid, i, j - 1);

        visit(grid, i, j + 1);

    }

}

所有递归算法都可以用循环来实现。示例之一如下。该解决方案实现了 BFS（广度优先搜索）算法，更多详情请参见维基百科。

class Solution {

  public int numIslands(char[][] grid) {

    if (grid == null || grid.length == 0) {

      return 0;

    }

    int nr = grid.length;

    int nc = grid[0].length;

    int num_islands = 0;

    for (int r = 0; r < nr; ++r) {

      for (int c = 0; c < nc; ++c) {

        if (grid[r][c] == '1') {

          ++num_islands;

          grid[r][c] = '0'; // mark as visited

          Queue<Integer> neighbors = new LinkedList<>();

          neighbors.add(r * nc + c);

          while (!neighbors.isEmpty()) {

            int id = neighbors.remove();

            int row = id / nc;

            int col = id % nc;

            if (row - 1 >= 0 && grid[row-1][col] == '1') {

              neighbors.add((row-1) * nc + col);

              grid[row-1][col] = '0';

            }

            if (row + 1 < nr && grid[row+1][col] == '1') {

              neighbors.add((row+1) * nc + col);

              grid[row+1][col] = '0';

            }

            if (col - 1 >= 0 && grid[row][col-1] == '1') {

              neighbors.add(row * nc + col-1);

              grid[row][col-1] = '0';

            }

            if (col + 1 < nc && grid[row][col+1] == '1') {

              neighbors.add(row * nc + col+1);

              grid[row][col+1] = '0';

            }

          }

        }

      }

    }

    return num_islands;

  }

}

Answer 2

问题出在这个函数上

public static void findObjects(int xCord, int yCord) {

        for(int y = yCord - 1; y <= yCord + 1; y++) {

          for(int x = xCord - 1; x <= xCord + 1; x++) {

            if(x > -1 && y > -1 && x < dotMap[0].length && y < dotMap.length) {

              if((x != xCord || y != yCord) && dotMap[x][y] == true && visited[x][y] != true) {

                visited[x][y] = true;

                 findObjects(x,y);

                //System.out.println("test");

              }

            }

          }

        }

      }`

在这里，您正在构建对findobjects的递归调用堆栈，并且最终它没有终止条件，因此最终以无限堆栈findobjects 结束，所以我的解决方案是，如果您只是检查 x 和 y 变量是否不相等并已访问[ x][y] 不为真，则无需调用递归，只需注释递归调用，因为您的循环已经执行了您希望递归调用执行的操作。

 public static void findObjects(int xCord, int yCord) {

        for(int y = yCord - 1; y <= yCord + 1; y++) {

          for(int x = xCord - 1; x <= xCord + 1; x++) {

            if(x > -1 && y > -1 && x < dotMap[0].length && y < dotMap.length) {

              if((x != xCord || y != yCord) && dotMap[x][y] == true && visited[x][y] != true) {

                visited[x][y] = true;

                //findObjects(x,y);

                //System.out.println("test");

              }

            }

          }

        }

      }