leetcode number of islands为什么不能用BFS?# JobHunting - 待字闺中
j*3
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行后
,电脑死机。。。
自己拖下来放到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
Queue
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行后
,电脑死机。。。