x*****0 发帖数: 452 | 1 给定一个n*n的board里面是0或1.算出里面独立0group的数量。比如
0 0 1 1 1
0 1 1 1 0
1 1 1 1 0
1 0 1 1 1
1 1 1 1 1
我的两个想法:
第一个当然就是DFS,bfs也行。每次遇到0的时候,进行DFS,得到一个connected
component。在DFS的过程中,把当前这个connected component的label改成count,
count初始化为1。并且DFS之后,count++。伪代码如下:
void dfs(int[][n] board, int row, int col, int count){
...
}
numofcp(board) {
count = 1;
for i = 1 : n
for j = 1 : n
if (board[i][j] == 0) {
dfs(i, j, count);
++count;
}
end
end
return count;
}
因为DFS的过程中,我们得用一个二维visited数组来标示已经访问过的元素。而每一次
进行DFS之前,都必须初始化这个visited数组。这个算法的时间复杂就有两部分组成:
numofcp*n*n(初始化visited) + number of elements having value 0 (DFS)
大家觉得呢? 似乎瓶颈反而在初始化visited数组这一部分。有什么更快的方法来标示
已访问过得元素这个问题吗?
方法2:
为了解释这个算法,我们先把board中的1换成-1。这样的预处理不是必须的。
two-pass algorithm
第一遍pass,从左上角往右下角扫描。同样初始化count = 1, 检查每个0的
neighbours。2种情况。 (1) 都是0或-1, 那么label当前元素为count (2) 如果
neighbours中有已经labeled,label 当前元素为其中较小的。
第二遍pass, 从右下角往左上角扫描。对于每个非-1的元素,检查neighbours的label
,如果有较小的,改变当前元素的label。
这样两遍之后,所有的connected component就已经被标示好了。在第二遍时,可以用
一个set来记录用了多少个label,这就是最后的结果。
大家帮忙看看,算法的正确性。以及更好的算法。 | x*****0 发帖数: 452 | | l*n 发帖数: 529 | 3 没看明白你到底想怎么优化。反正就是o(n^2)的,你是在想优化系数么?visited不是
每次都要初始化,一遍就够了。 | x*****0 发帖数: 452 | 4 就是想优化初始化,因为开始认为要多次。就想着能不能优化。现在只要一次,就没有
必要了。thanks。
【在 l*n 的大作中提到】 : 没看明白你到底想怎么优化。反正就是o(n^2)的,你是在想优化系数么?visited不是 : 每次都要初始化,一遍就够了。
| x*****0 发帖数: 452 | 5 问一个不想关的问题,为什么我的帖子不能在版面中找到呀?
【在 l*n 的大作中提到】 : 没看明白你到底想怎么优化。反正就是o(n^2)的,你是在想优化系数么?visited不是 : 每次都要初始化,一遍就够了。
| x*****0 发帖数: 452 | 6 对于DFS的解法,不需要visited数组。
直接把访问过的改成count就行了,最后就输出count
谢啦。 | g****r 发帖数: 74 | 7 static int count = 1;
public static int numComponents(int[][] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, i, j, count))
count++;
}
}
return count - 1;
}
public static boolean dfs(int[][] board, int i, int j, int c) {
if (i >= board.length || j >= board[0].length || i < 0 || j < 0)
return false;
if (board[i][j] > 0)
return false;
board[i][j] = c;
dfs(board, i - 1, j, c);
dfs(board, i + 1, j, c);
dfs(board, i, j - 1, c);
dfs(board, i, j + 1, c);
return true;
} | s*****r 发帖数: 108 | | s*****n 发帖数: 169 | 9 不用那么复杂。走一遍就行。
public static void main(String[] args) {
int[][] m=new int[][]{{0,0,1,1,1},{0,1,1,1,0},{1,1,1,1,0},{1,0,1,1,1
},{1,1,1,1,1}};
//int[][] m=new int[][]{{0,0,1,1,1},{0,0,1,1,0},{1,1,1,1,1},{1,1,1,1
,1},{1,1,1,1,1}};
System.out.println(getNumberOf0Groups(m,5,5) );
}
public static int getNumberOf0Groups(int[][] m, int col, int row) {
int count = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (m[i][j] == 0 && !isNeigbor0(m, i, j)) {
count++;
}
}
}
return count;
}
public static boolean isNeigbor0(int[][] m, int i, int j) {
boolean upRowHas0=false;
boolean leftColHas0=false;
//check row
if (i - 1 >=0) {
upRowHas0 = (m[i - 1][j] == 0);
System.out.println((i-1)+" "+j);
}
//check col
if (j - 1 >=0) {
leftColHas0 = (m[i][j - 1] == 0);
System.out.println(i+" "+(j-1));
}
return upRowHas0|| leftColHas0;
} | h**6 发帖数: 4160 | 10 以前写过很多遍相同的代码,做竞赛题的时候,找出各个联通部分往往是第一步内容,
然后再对每一联通部分求解。 | e********r 发帖数: 2352 | 11 这个很简练哈.
,1
,1
【在 s*****n 的大作中提到】 : 不用那么复杂。走一遍就行。 : public static void main(String[] args) { : int[][] m=new int[][]{{0,0,1,1,1},{0,1,1,1,0},{1,1,1,1,0},{1,0,1,1,1 : },{1,1,1,1,1}}; : //int[][] m=new int[][]{{0,0,1,1,1},{0,0,1,1,0},{1,1,1,1,1},{1,1,1,1 : ,1},{1,1,1,1,1}}; : System.out.println(getNumberOf0Groups(m,5,5) ); : } : public static int getNumberOf0Groups(int[][] m, int col, int row) { : int count = 0;
| e***l 发帖数: 710 | 12 111111
101101
101101
000000
数出来几个? | H**r 发帖数: 10015 | 13 啥叫独立0
【在 x*****0 的大作中提到】 : 给定一个n*n的board里面是0或1.算出里面独立0group的数量。比如 : 0 0 1 1 1 : 0 1 1 1 0 : 1 1 1 1 0 : 1 0 1 1 1 : 1 1 1 1 1 : 我的两个想法: : 第一个当然就是DFS,bfs也行。每次遇到0的时候,进行DFS,得到一个connected : component。在DFS的过程中,把当前这个connected component的label改成count, : count初始化为1。并且DFS之后,count++。伪代码如下:
|
|