关于使用并查集实现leetcode200号问题
来源:6-7 Flood Fill 的更多优化
martin123_
2019-09-20
老师您好,关于这个问题,我在您提供的695号问题并查集的实现方法的基础上,对代码进行了一定的修改,想法是这样的:
对于岛屿,就按照一般思路寻找其邻点并将他们union;对于海的部分,就将其与某个固定的索引union(事实上我对union多开了一个空间:RC + 1,这个索引指RC),最后在通过对并查集parent数组的扫描,将其中根不是R*C的元素加入一个集合再返回该元素的大小;不知道这个思路是否正确?以下是我的代码(错误的),如果思路错误能否请老师指点别的思路?
//leetcode 200, 使用并查集
import java.util.TreeSet;
class Solution {
private class UF{
private int[] parent;
public UF(int capacity){
parent = new int[capacity];
for(int i = 0; i < capacity; i ++)
parent[i] = i;
}
public int find(int p){
if(parent[p] != p)
parent[p] = find(parent[p]);
return parent[p];
}
public boolean isConnected(int s, int t){return find(s) == find(t);}
public void unionElements(int s, int t){
int sRoot = find(s);
int tRoot = find(t);
if(sRoot == tRoot) return;
parent[sRoot] = tRoot;
}
public int treeNumber(){
TreeSet<Integer> set = new TreeSet<>();
for(int i = 0; i < parent.length; i ++){
int x = find(i);
if(x != parent.length - 1)
set.add(x);
}
return set.size();
}
}
private int R, C;
private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public int numIslands(char[][] grid) {
if(grid == null) return 0;
R = grid.length;
if(R == 0) return 0;
C = grid.length;
if(C == 0) return 0;
UF uf = new UF(R * C + 1);
for(int v = 0; v < R * C; v ++){
int x = v / C, y = v % C;
if(grid[x][y] == 1)
for(int d = 0; d < 4; d ++){
int netx = x + dirs[d][0], nety = y + dirs[d][1];
if(inArea(netx, nety) && grid[netx][nety] == 1)
uf.unionElements(v, netx*C + nety);
}
else
uf.unionElements(v, R*C);
}
return uf.treeNumber();
}
private boolean inArea(int x, int y){return x >= 0 && x < R && y >= 0 && y < C;}
}
感觉在这种实现中,关键可能是没有对海那部分做特殊处理,而海部分的索引在并查集中也充当了节点的身份,导致不能直接得到联通分量的具体个数;并且也不像是图dfs遍历那样一口气遍历完一个联通分量,而是每次只遍历一个结点与它的相邻节点,很难使用一个count来对每次遍历进行计数
写回答
1回答
-
liuyubobobo
2019-09-21
思路是对的。
1)C = grid[0].length;
2)grid 里的元素是 char,不是 int
继续加油。
012019-09-21
相似问题