我對(duì)導(dǎo)致堆棧溢出錯(cuò)誤的原因進(jìn)行了一些研究，我可以得出結(jié)論，它是由程序中的遞歸函數(shù)引起的，該函數(shù)應(yīng)該“計(jì)算數(shù)組中的島數(shù)”。我明白是什么導(dǎo)致了這個(gè)問(wèn)題，但不確定為什么會(huì)發(fā)生這種情況，或者我的主要問(wèn)題是實(shí)際該怎么做。我發(fā)現(xiàn)如果我通過(guò)讓程序反復(fù)向控制臺(tái)打印一些東西來(lái)減慢程序的速度，它可以工作，但需要很長(zhǎng)時(shí)間才能完成。有沒(méi)有辦法可以保持程序速度而不會(huì)出錯(cuò)，或者有更好的方法來(lái)解決問(wèn)題（搜索“島數(shù)”以找到問(wèn)題）。此外，該數(shù)組是二維的，大小為 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; }}
2 回答
郎朗坤
TA貢獻(xiàn)1921條經(jīng)驗(yàn) 獲得超9個(gè)贊
在您的示例中，每次調(diào)用都會(huì)findObjects從循環(huán)中將 2 個(gè)變量添加到堆棧 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);
}
}
所有遞歸算法都可以用循環(huán)來(lái)實(shí)現(xiàn)。示例之一如下。該解決方案實(shí)現(xiàn)了 BFS（廣度優(yōu)先搜索）算法，更多詳情請(qǐng)參見(jiàn)維基百科。
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;
}
}
溫溫醬
TA貢獻(xiàn)1752條經(jīng)驗(yàn) 獲得超4個(gè)贊
問(wèn)題出在這個(gè)函數(shù)上
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");
}
}
}
}
}`
在這里，您正在構(gòu)建對(duì)findobjects的遞歸調(diào)用堆棧，并且最終它沒(méi)有終止條件，因此最終以無(wú)限堆棧findobjects 結(jié)束，所以我的解決方案是，如果您只是檢查 x 和 y 變量是否不相等并已訪問(wèn)[ x][y] 不為真，則無(wú)需調(diào)用遞歸，只需注釋遞歸調(diào)用，因?yàn)槟难h(huán)已經(jīng)執(zhí)行了您希望遞歸調(diào)用執(zhí)行的操作。
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");
}
}
}
}
}
添加回答
舉報(bào)
0/150
提交
取消