由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 讨论一道面试题--number of connected components
相关主题
codility一道题shortest path in matrix
问一道面试题目[难题求助] leetcode wordsearch
问一个reference couting的smart point的问题Amazon电面纪实
问一道算法题被问到一个题目
google 一题F家一题
请教个面试题目Word Search large case TLE
一道G题贡献A家面经
贡献某公司onsite面经问两道面试中碰到的题目
相关话题的讨论汇总
话题: int话题: dfs话题: count话题: board话题: static
进入JobHunting版参与讨论
1 (共1页)
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
2
自己顶一个。
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
8
board 改 1 不用 visit
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++。伪代码如下:

1 (共1页)
进入JobHunting版参与讨论
相关主题
问两道面试中碰到的题目google 一题
请教一下,leetcode surrounded regions这题为什么我的代码会超时请教个面试题目
word search BST 解法,大测试超时,请大家指点迷津一道G题
T家online test跪了大家帮忙看看题贡献某公司onsite面经
codility一道题shortest path in matrix
问一道面试题目[难题求助] leetcode wordsearch
问一个reference couting的smart point的问题Amazon电面纪实
问一道算法题被问到一个题目
相关话题的讨论汇总
话题: int话题: dfs话题: count话题: board话题: static