6/7, Union-Find, 并查集应用
Graph Valid Tree
开始做题之前，要注意先把定义和可能的各种 test case 正确输出弄清楚。在 LeetCode 上就只能反复提交试错，但是面试的时候，做题之前这些都是要通过交流去问清楚的，要么后面会浪费很多时间去涂涂改改，甚至发现一开始就答错了。。
给定一个 Set of Nodes ，Tree 要满足两个条件：
- 无环
- 单 root 节点
把这两点搞清楚之后，这题就很简单了。先一个一个 edge 去加，如果发现有环的话直接返回 false；否则跑到最后，看看最终的 number of connected components 是不是 1.
public class Solution {
private class WeightedUnionFind{
HashMap<Integer, Integer> parent;
HashMap<Integer, Integer> size;
boolean hasCycle;
int count;
public WeightedUnionFind(int n){
parent = new HashMap<Integer, Integer>();
size = new HashMap<Integer, Integer>();
hasCycle = false;
count = n;
for(int i = 0; i < n; i++){
parent.put(i, i);
size.put(i, 1);
}
}
public Integer find(Integer node){
if(!parent.containsKey(node)) return null;
Integer root = node;
while(root != parent.get(root)){
root = parent.get(root);
}
while(node != root){
Integer next = parent.get(node);
parent.put(node, root);
node = next;
}
return root;
}
public void union(Integer nodeA, Integer nodeB){
Integer rootA = find(nodeA);
Integer rootB = find(nodeB);
if(rootA == null || rootB == null) return;
if(rootA.equals(rootB)) {
hasCycle = true;
return;
}
int sizeA = size.get(rootA);
int sizeB = size.get(rootB);
if(sizeA > sizeB){
parent.put(rootB, rootA);
size.put(rootA, sizeA + sizeB);
} else {
parent.put(rootA, rootB);
size.put(rootB, sizeA + sizeB);
}
count --;
}
public boolean hasCycle(){
return this.hasCycle;
}
public boolean isTree(){
return (!this.hasCycle) && (count == 1);
}
}
public boolean validTree(int n, int[][] edges) {
if(edges == null || edges.length == 0){
if(n > 1) return false;
else return true;
}
WeightedUnionFind uf = new WeightedUnionFind(n);
for(int i = 0; i < edges.length; i++){
int nodeA = edges[i][0];
int nodeB = edges[i][1];
uf.union(nodeA, nodeB);
if(uf.hasCycle()) return false;
}
return uf.isTree();
}
}
这道题BFS也可以做, 从任一源点出发, BFS判断是否有环, 最后通过vis[]数组判断是否所有点都访问到, 如果是, 则只有一个connected component, 返回true
public class Solution {
public boolean validTree(int n, int[][] edges) {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
for(int i=0;i<n;i++){
ArrayList<Integer> l = new ArrayList<Integer>();
map.put(i, l);
}
for(int i=0;i<edges.length;i++){
map.get(edges[i][0]).add(edges[i][1]);
map.get(edges[i][1]).add(edges[i][0]);
}
Queue<Integer> q = new LinkedList<Integer>();
boolean[] vis = new boolean[n];
q.offer(0);
while(!q.isEmpty()){
int node = q.poll();
if(vis[node])
return false;
vis[node] = true;
for(int neighbors : map.get(node)){
map.get(neighbors).remove(new Integer(node)); //key point
q.offer(neighbors);
}
}
for(int i=0;i<n;i++) //don't forget
if(!vis[i])
return false;
return true;
}
}
Surrounded Regions
第一次写的时候用了个 HashSet 记录哪些点访问过，显得麻烦，还浪费了额外空间。
这种在矩阵上做 flood filling 的问题，可以靠自定义字符做标记，取代用额外空间的记录方式。
这段代码的逻辑就是从四个边开始碰到 'O' 就往里扫，把扫到的都标上 'S' 代表有效湖；最后过一遍的时候除了 'S' 的都标成 'X' 就好了。
然而在大矩阵上 stackoverflow... 看来无脑 dfs 的做法还不够经济啊。。。
public class Solution {
public void solve(char[][] board) {
if(board ==null || board.length==0||board[0].length==0) return;
int m = board.length; int n = board[0].length;
for(int i=0;i<m;i++){
if(board[i][0]=='O')
dfs(board, i, 0);
if(board[i][n-1]=='O')
dfs(board, i, n-1);
}
for(int j=0;j<n;j++){
if(board[0][j]=='O')
dfs(board, 0, j);
if(board[m-1][j]=='O')
dfs(board, m-1, j);
}
for(int i=0;i<m;i++)
for(int j=0;j<n;j++){
if(board[i][j]=='O'){
board[i][j] = 'X';
}
if(board[i][j]=='#'){
board[i][j] = 'O';
}
}
}
public void dfs(char[][] board, int i, int j){
int m = board.length; int n = board[0].length;
if(i<0||i>=m||j<0 ||j>=n || board[i][j]=='X') return;
board[i][j] = '#';
if(i>1)
dfs(board, i-1,j);
if(j>1)
dfs(board, i+1,j);
if(i+1<m)
dfs(board, i,j-1);
dfs(board, i,j+1);
}
}
这题当然也可以用 Union-Find 写，先把所有最外圈的 boundry 连上，然后把里面的相邻 'O' 做 union，最后扫矩阵的时候，如果对应的 root 不是 boundry root 就留下，不然都改成 'X'.+
不过只是在这个问题上，不是很简洁。
Number of Islands II (G)
这个问题实际上只需要findroot， union部分在主体里面。
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> ans = new ArrayList<Integer>();
if(m==0 || n==0) return ans;
int[][] matrix = new int[m][n];
int[][] dist = {{-1, 0}, {0,-1}, {0,1}, {1,0}};
int[] root = new int[m*n];
int[][] grid = new int[m][n];
int count = 0;
Arrays.fill(root, -1);
for(int i=0;i<positions.length;i++){
int x = positions[i][0]; int y = positions[i][1];
count++; int id = x*n+y;
root[id] = id;
grid[x][y]=1;
for(int[] d : dist){
int nx = x+d[0]; int ny = y+d[1];
if(nx>=0 && nx<m && ny>=0 && ny<n &&grid[nx][ny]==1){
int nroot = find(nx*n+ny, root);
int idroot = find(id, root);
if(nroot!=idroot){
root[nroot] = idroot;
count--;
}
}
}
ans.add(count);
}
return ans;
}
public int find(int x, int[] root){
while(root[x]!=x) x= root[x];
return x;
}