d*********g
发帖数: 38 | 1 可以过80%的test cases，一个很大的grid结果总是差1。哪位高人看看下面code逻辑有
什么问题吗？不超时。刚才上eclipse跑，数1数的眼睛都快瞎了。
public int numIslands(char[][] grid) {
if(grid==null || grid.length==0 || grid[0].length==0)
return 0;
int row=grid.length, col=grid[0].length;
int res=0;
for(int i=0; i
for(int j=0; j
if(grid[i][j]=='1'){
bfs(i, j, grid);
res++;
}
}
}
return res;
}
public void bfs(int i, int j, char[][] grid){
int row=grid.length, col=grid[0].length;
Queue q=new LinkedList();
int pos=i*col+j;
q.offer(pos);
while(!q.isEmpty()){
int n=q.poll();
int px=n/col, py=n%col;
if(px<0 || px>=row || py<0 || py>=col || grid[px][py]=='0')
continue;
else{
grid[px][py]='0';
q.offer((px+1)*col+py);
q.offer((px-1)*col+py);
q.offer(px*col+py+1);
q.offer(px*col+py-1);
}
}
} |
d********o
发帖数: 23 | 2 int pos=i*col+j;
q.offer((px+1)*col+py);
q.offer((px-1)*col+py);
q.offer(px*col+py+1);
q.offer(px*col+py-1);
}
会越界的
这种编码需要col + 1, row + 1 |
d*********g
发帖数: 38 | 3 从queue取出的时候已经做了check了
if(px<0 || px>=row || py<0 || py>=col || grid[px][py]=='0')
continue;
另外oj也没有报越界的错。
【在 d********o 的大作中提到】
: int pos=i*col+j;
: q.offer((px+1)*col+py);
: q.offer((px-1)*col+py);
: q.offer(px*col+py+1);
: q.offer(px*col+py-1);
: }
: 会越界的
: 这种编码需要col + 1, row + 1
|
j******8
发帖数: 105 | 4 最后有问题，
q.offer((px+1)*col+py);
q.offer((px-1)*col+py);
q.offer(px*col+py+1);
q.offer(px*col+py-1);//px=1, py=0 will still give valid n
here which is wrong
改成这样
if(px+1
if(px-1>=0) q.add((px-1)*col+py);
if(py+1
if(py-1>=0) q.add(px*col+py-1);
算法本身就是错的，过了的cases是运气
【在 d*********g 的大作中提到】
: 可以过80%的test cases，一个很大的grid结果总是差1。哪位高人看看下面code逻辑有
: 什么问题吗？不超时。刚才上eclipse跑，数1数的眼睛都快瞎了。
: public int numIslands(char[][] grid) {
: if(grid==null || grid.length==0 || grid[0].length==0)
: return 0;
: int row=grid.length, col=grid[0].length;
: int res=0;
: for(int i=0; i: for(int j=0; j: if(grid[i][j]=='1'){
|
d*********g
发帖数: 38 | |
d********o
发帖数: 23 | 6 这就是版上说的，帮了也不会感激
Good luck with your future :)
【在 d*********g 的大作中提到】
: 这下明白了，看来确实有越界。
|
d*********g
发帖数: 38 | 7 谢谢duckduckgo，你的回答也是对的，只是一开始没有看明白。
大家在这里耐心看别人的代码（有时候是乱码）解答，至少对我来说很不容易。job版
回贴的都是活雷锋。 |
