Union-Find, 并查集应用
开始做题之前，要注意先把定义和可能的各种 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();
}
}第一次写的时候用了个 HashSet 记录哪些点访问过，显得麻烦，还浪费了额外空间。
这种在矩阵上做 flood filling 的问题，可以靠自定义字符做标记，取代用额外空间的记录方式。
这段代码的逻辑就是从四个边开始碰到 'O' 就往里扫，把扫到的都标上 'S' 代表有效湖；最后过一遍的时候除了 'S' 的都标成 'X' 就好了。
然而在大矩阵上 stackoverflow... 看来无脑 dfs 的做法还不够经济啊。。。
public class Solution {
public void solve(char[][] board) {
if(board == null || board.length == 0) return;
int rows = board.length;
int cols = board[0].length;
for(int i = 0; i < cols; i++){
if(board[0][i] == 'O'){
dfs(board, 0, i);
}
if(board[rows - 1][i] == 'O'){
dfs(board, rows - 1, i);
}
}
for(int i = 1; i < rows - 1; i++){
if(board[i][0] == 'O'){
dfs(board, i, 0);
}
if(board[i][cols - 1] == 'O'){
dfs(board, i, cols - 1);
}
}
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(board[i][j] == 'S'){
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
}
private void dfs(char[][] board, int row, int col){
if(row < 0 || row >= board.length) return;
if(col < 0 || col >= board[0].length) return;
if(board[row][col] != 'O') return;
board[row][col] = 'S';
dfs(board, row + 1, col);
dfs(board, row - 1, col);
dfs(board, row, col + 1);
dfs(board, row, col - 1);
}
}写了个 BFS 的在一个中型矩阵上 TLE了，我有点方。。
public class Solution {
public void solve(char[][] board) {
if(board == null || board.length == 0) return;
int rows = board.length;
int cols = board[0].length;
Queue<Integer> queue = new LinkedList<Integer>();
for(int i = 0; i < cols; i++){
if(board[0][i] == 'O'){
queue.offer(i);
bfs(board, 0, i, queue);
}
if(board[rows - 1][i] == 'O'){
queue.offer((rows - 1) * cols + i);
bfs(board, rows - 1, i, queue);
}
}
for(int i = 1; i < rows - 1; i++){
if(board[i][0] == 'O'){
queue.offer(i * cols);
bfs(board, i, 0, queue);
}
if(board[i][cols - 1] == 'O'){
queue.offer(i * cols + cols - 1);
bfs(board, i, cols - 1, queue);
}
}
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(board[i][j] == 'S'){
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
}
private void bfs(char[][] board, int row, int col, Queue<Integer> queue){
int rows = board.length;
int cols = board[0].length;
if(!isValid(row, rows, col, cols)) return;
while(!queue.isEmpty()){
Integer index = queue.poll();
int x = index / cols;
int y = index % cols;
if(board[x][y] == 'O') board[x][y] = 'S';
if(isValid(x + 1, rows, y, cols) && board[x + 1][y] == 'O') queue.offer((x + 1) * cols + y);
if(isValid(x - 1, rows, y, cols) && board[x - 1][y] == 'O') queue.offer((x - 1) * cols + y);
if(isValid(x, rows, y + 1, cols) && board[x][y + 1] == 'O') queue.offer(x * cols + y + 1);
if(isValid(x, rows, y - 1, cols) && board[x][y - 1] == 'O') queue.offer(x * cols + y - 1);
}
return;
}
private boolean isValid(int row, int rows, int col, int cols){
if(row < 0 || row >= rows) return false;
if(col < 0 || col >= cols) return false;
return true;
}
}同样的 DFS 逻辑，做了如下改动之后就不会 stackoverflow 了：
DFS 时不进入最外围一圈的位置
简单来讲是在尽可能限制 DFS call stack 的层数，控制 DFS 的深度。从正确性上讲，上面的写法也是正确的，但是在极端情况下如果某一个从边沿出发的 DFS 连通了另一个边沿出发的 DFS，会导致一次的搜索路径非常长，于是 stackoverflow. 既然边沿的格子无论如何都要检查一遍，就把外圈封住，减少每个起点的 search tree depth.
public class Solution {
public void solve(char[][] board) {
if(board == null || board.length == 0) return;
int rows = board.length;
int cols = board[0].length;
for(int i = 0; i < cols; i++){
if(board[0][i] == 'O'){
dfs(board, 0, i);
}
if(board[rows - 1][i] == 'O'){
dfs(board, rows - 1, i);
}
}
for(int i = 1; i < rows - 1; i++){
if(board[i][0] == 'O'){
dfs(board, i, 0);
}
if(board[i][cols - 1] == 'O'){
dfs(board, i, cols - 1);
}
}
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(board[i][j] == 'S'){
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
}
private void dfs(char[][] board, int row, int col){
if(row < 0 || row >= board.length) return;
if(col < 0 || col >= board[0].length) return;
if(board[row][col] != 'O') return;
board[row][col] = 'S';
// DFS 时不进入最外圈
if(row + 2 < board.length && board[row + 1][col] == 'O') dfs(board, row + 1, col);
if(row - 2 >= 0 && board[row - 1][col] == 'O') dfs(board, row - 1, col);
if(col + 2 < board[0].length && board[row][col + 1] == 'O') dfs(board, row, col + 1);
if(col - 2 >= 0 && board[row][col - 1] == 'O') dfs(board, row, col - 1);
}
}这题当然也可以用 Union-Find 写，先把所有最外圈的 boundry 连上，然后把里面的相邻 'O' 做 union，最后扫矩阵的时候，如果对应的 root 不是 boundry root 就留下，不然都改成 'X'.
不过只是在这个问题上，不是很简洁。
Last updated
