j**********3
发帖数: 3211 | 1 我的代码，Time Limit Exceeded.
自己拖下来放到eclipse里边，跑到死机了。。。到底哪里出错了？
public int numIslands(char[][] grid) {
if(grid == null){
return 0;
}
int m = grid.length;
if(m == 0){
return 0;
}
int n = grid[0].length;
char c = 'A';
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if (grid[i][j] == '1') {
bfs(grid, i, j, c, m, n);
c = (char)(c + 1);
}
}
}
return c - 'A';
}
public void bfs(char[][] grid, int i, int j, char c, int m, int n){
Queue q1 = new LinkedList();
Queue q2 = new LinkedList();
q1.add(i);
q2.add(j);
while(!q1.isEmpty()){
int a = q1.poll();
int b = q2.poll();
grid[a][b] = (char)(c + 1);
if(a - 1 >=0 && grid[a - 1][b] == '1'){
q1.add(a - 1);
q2.add(b);
}
if(a + 1 < m && grid[a + 1][b] == '1'){
q1.add(a + 1);
q2.add(b);
}
if(b - 1 >= 0 && grid[a][b - 1] == '1'){
q1.add(a);
q2.add(b - 1);
}
if(b + 1 < n && grid[a][b + 1] == '1'){
q1.add(a);
q2.add(b + 1);
}
}
}
用了这个超级长的test case：
["11111011111111101011","01111111111110111110","10111001101111111111","
11110111111111111111","10011111111111111111","10111111011101110111","
01111111111101101111","11111111111101111011","11111111110111111111","
11111111111111111111","01111111011111111111","11111111111111111111","
11111111111111111111","11111011111110111111","10111110111011110111","
11111111111101111110","11111111111110111100","11111111111111111111","
11111111111111111111","11111111111111111111"]
就挂了。。。。我试着把test case的后3行去掉，发现可以work啊。。。加上后3行后
，电脑死机。。。 | s****a
发帖数: 794 | | j**********3
发帖数: 3211 | 3 告诉我吧，告诉我吧。。。
【在 s****a 的大作中提到】
: 看出来也不该告诉你啊 调试啊！
| s******7
发帖数: 1758 | 4 bfs每次走完一个queue需要一个数组来记录访问过没有，这又不是tree, 好多格子重复
访问, 回去好好看看bfs吧，这是基本功 | r*g
发帖数: 186 | 5 我用bfs没出现问题啊
【在 j**********3 的大作中提到】
: 我的代码，Time Limit Exceeded.
: 自己拖下来放到eclipse里边，跑到死机了。。。到底哪里出错了？
: public int numIslands(char[][] grid) {
: if(grid == null){
: return 0;
: }
: int m = grid.length;
: if(m == 0){
: return 0;
: }
| j********g
发帖数: 80 | 6 while loop 里 Add进Q的时候就要set格子等于c + 1， 否则就重复加了好多 | j**********3
发帖数: 3211 | 7 我看到这个了，但我改了grid里边走过的值，所以就不是1了，不会再visit它了。
【在 s******7 的大作中提到】
: bfs每次走完一个queue需要一个数组来记录访问过没有，这又不是tree, 好多格子重复
: 访问, 回去好好看看bfs吧，这是基本功
| j**********3
发帖数: 3211 | 8 哦。。。我也想到可能是那里出问题，但如果用recursion的方法，也是call了之后再
变grid里边的值啊。。。
----知道了知道了。。。
【在 j********g 的大作中提到】
: while loop 里 Add进Q的时候就要set格子等于c + 1， 否则就重复加了好多
| r*g
发帖数: 186 | 9 recursion通不过的
后面有的问题规模非常大
会stack overflow的
【在 j**********3 的大作中提到】
: 哦。。。我也想到可能是那里出问题，但如果用recursion的方法，也是call了之后再
: 变grid里边的值啊。。。
: ----知道了知道了。。。
| j**********3
发帖数: 3211 | 10 确实是这个问题
【在 r*g 的大作中提到】
: recursion通不过的
: 后面有的问题规模非常大
: 会stack overflow的
|
|
