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

Question

我对导致堆栈溢出错误的原因做了一些研究，我可以得出结论，它是由程序中的递归函数引起的，该函数应该在数组中 "count the number of islands"。我了解导致问题的原因，但不确定为什么会发生这种情况，或者我的主要问题是实际如何处理。我发现，如果我通过让它反复向控制台打印一些东西来减慢程序速度，它就可以工作，但它需要很长时间才能完成。有没有什么方法可以保持程序速度不出错，或者有更好的方法来解决问题（向上搜索 "number of islands" 找到问题）。此外，数组是二维的，大小为 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

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

最快的解决方案之一：

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（广度优先搜索）算法，更多细节见 wikipedia。

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[= 的无限堆栈18=]，所以我的解决方案是，如果您只是检查 x 和 y 变量是否不相等且 visited[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"); } } } } }

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

Stack Overflow Error in a Self Calling Function in Java (Number of Islands)

java

recursion

count

self

gaps-and-islands