Union Find (Java) - ShuweiLeung/Thinking GitHub Wiki

1.（721:Medium）（非常非常经典题）Accounts Merge

  • 该题使用Union Find去求解
  1. The key task here is to connect those emails, and this is a perfect use case for union find.
  2. to group these emails, each group need to have a representative, or parent.
  3. At the beginning, set each email as its own representative.
  4. Emails in each account naturally belong to a same group, and should be joined by assigning to the same parent (let's use the parent of first email in that list);
a b c // now b, c have parent a
d e f // now e, f have parent d
g a d // now abc, def all merged to group g

parents populated after parsing 1st account: a b c

a->a
b->a
c->a

parents populated after parsing 2nd account: d e f

d->d
e->d
f->d

parents populated after parsing 3rd account: g a d

g->g
a->g
d->g
  • 我们在union后，以根节点作为代表将以它为根的所有元素都存入一个相同的集合里，这里使用TreeSet，即可以过滤重复，又可以自动排序。在归并过程中，注意以下问题：

What if the emails of accounts are like:

a m n
b m r
c r q

then the parent for 1st account is:

a -> a
m -> a
n -> a

the parent for the 2nd account is:

b -> b
m -> b
r -> b

and the parent for the 3rd account is:

c -> c
r -> c
q -> c

How are the emails linked in such case?

when you try to link m to b, you are not linking m, you are linking m's parent which is a to b. so in the end, all of these will be linked to c, you can check Union Find data structure.

所以，要注意在归并过程中是将一个元素的根节点归并到另一个元素的根节点上。而不是仅局限于两个元素之间的操作。

  • 具体思路请参看代码实现及注释。该题还有BFS的解法，可以参看。

2.（947:Medium）（非常非常经典题）Most Stones Removed with Same Row or Column

  • 如果两个石头在同行或者同列，两个石头就是连接的。连在一起的石头，可以组成一个连通图。每一个连通图至少会剩下1个石头。所以我们希望存在一种思路，每个连通图都只剩下1个石头。这样这题就转化成了数岛屿的问题。所以我们用一个字符串"stone[0]+' ' + stone[1]"来表示一个石头，当两个石头的行index或列index相同时，就将其union。
  • 更高效的解法：我们总是看成一个石头被分配了(i,j)两个index，但我们可以转换一下看问题的角度，i、j两个index是独立的两个index，被stone所连接，因而他们可以被union在一起。我们的输入是所有的石头，每个石头都固定连接两个元素，一个石头把它所在行列坐标连在了一起。

上面的实现方法需要嵌套遍历两次stones数组O(n^2)的时间复杂度，比较耗时，discuss里还有其他更高效的方法，可以只需要遍历一次数组O(n)时间复杂度解决问题，但没有看懂，好像用到了补码

3.（803:Hard）（非常非常经典题）Bricks Falling When Hit

  • 这道题给了我们一个由0和1组成的grid，说是1代表砖头，当砖头连着顶端的时候，就不会掉落，当某个砖头连着不会掉落的砖头时，其本身也不会掉落。然后我们要去掉一些砖头，当去掉某个砖头时，与其相连的砖头可能也会同时掉落。所以这里让我们求同时掉落的砖头个数。博主书读的不少，不会受骗，这尼玛不就是泡泡龙游戏么。其中泡泡龙的一大技巧就是挂葡萄，当关键节点处的泡泡被打掉后，这整个一串都可以直接掉下来。这里也是一样啊，grid的顶端就是游戏界面的顶端，然后砖头就是泡泡，去掉砖头就是消掉某个地方的泡泡，然后掉落的砖头就是掉下的泡泡啦。游戏玩的6，不代表题会做，其实这道题还是蛮有难度的，花了博主很长的时间。
  • 首先我们来想，我们肯定要统计出当前没有掉落的砖头数量，当去掉某个砖头后，我们可以统计当前还连着的砖头数量，二者做差值就是掉落的砖头数量。那么如何来统计不会掉落的砖头数量呢，由于顶层的砖头时不会掉落的，那么跟顶层相连的所有砖头肯定也不会掉落，我们就可以使用DFS来遍历，我们可以把不会掉落的砖头位置存入一个HashSet中，这样通过比较不同状态下HashSet中元素的个数，我们就知道掉落了多少砖头。然后我们再来想一个问题，在没有去除任何砖头的时候，我们DFS查找会遍历所有的砖头，当某个砖头去除后，可能没有连带其他的砖头，那么如果我们再来遍历一遍所有相连的砖头，相当于又把整个数组搜索了一遍，这样并不是很高效。我们可以试着换一个思路，如果我们先把要去掉的所有砖头都先去掉，这样我们遍历所有相连的砖头就是最终还剩下的砖头，然后我们从最后一个砖头开始往回加，每加一个砖头，我们就以这个砖头为起点，DFS遍历其周围相连的砖头，加入HashSet中，那么只会遍历那些会掉的砖头，那么增加的这些砖头就是会掉的砖头数量了，然后再不停的在增加前面的砖头，直到把hits中所有的砖头都添加回来了，那么我们也就计算出了每次会掉的砖头的个数。
  • 好，我们使用一个HashSet来保存不会掉落的砖头，然后先遍历hits数组，把要掉落的砖头位置的值都减去一个1，这里有个需要注意的地方，hits里的掉落位置实际上在grid中不一定有砖头，就是说可能是本身为0的位置，那么我们减1后，数组中也可能会有-1，没有太大的影响，不过需要注意一下，这里不能使用 if (grid[i][j]) 来直接判断其是否为1，因为非0值-1也会返回true。然后我们对第一行的砖头都调用递归函数，因为顶端的砖头不会掉落，跟顶端的砖头相连的砖头也不会掉落，所以要遍历所有相连的砖头，将位置都存入noDrop。然后就是从最后一个位置往前加砖头，先记录noDrop当前的元素个数，然后grid中对应的值自增1，之后增加后的值为1了，才说明这块之前是有砖头的，然后我们看其上下左右位置，若有砖头，则对当前位置调用递归，还有一种情况是当前是顶层的话，还是要调用递归。递归调用完成后二者的差值再减去1就是掉落的砖头数，减1的原因是去掉的砖头不算掉落的砖头数中，参见代码如下：
    public int[] hitBricks(int[][] grid, int[][] hits) {
	int m = grid.length, n = grid[0].length, k = hits.length;
	int[] res = new int[k];
	Set<Integer> noDrop = new HashSet<>();
	for (int i = 0; i < k; ++i) grid[hits[i][0]][hits[i][1]] -= 1;
	for (int i = 0; i < n; ++i) {
		if (grid[0][i] == 1) check(grid, 0, i, noDrop);
	}
	for (int i = k - 1; i >= 0; --i) {
		int oldSize = noDrop.size(), x = hits[i][0], y = hits[i][1];
		if (++grid[x][y] != 1) continue;
		if ((x - 1 >= 0 && noDrop.contains((x - 1) * n + y))  // 判断是否与其他nodrop不掉落的砖块相连，如果被击落的砖块本身就是要掉落的，那么加上它以后也不会多出来不会掉落的砖块
				|| (x + 1 < m && noDrop.contains((x + 1) * n + y))
				|| (y - 1 >= 0 && noDrop.contains(x * n + y - 1))
				|| (y + 1 < n && noDrop.contains(x * n + y + 1))
				|| x == 0) {
			check(grid, x, y, noDrop);
			res[i] = noDrop.size() - oldSize - 1;
		}
	}
	return res;
}

void check(int[][] grid, int i, int j, Set<Integer> noDrop) {
	int m = grid.length, n = grid[0].length;
	if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != 1 || noDrop.contains(i * n + j)) return;
	noDrop.add(i * n + j);
	check(grid, i - 1, j, noDrop);
	check(grid, i + 1, j, noDrop);
	check(grid, i, j - 1, noDrop);
	check(grid, i, j + 1, noDrop);
}
  • 若要用到连通分量的知识，可以具体参看下面的代码及注释
int[] dirs = new int[]{0, -1, 0, 1, 0};
int m;
int n;
int[][] g;
int seq;
int count;
	  
public int[] hitBricks(int[][] grid, int[][] hits) {
    this.g = grid;
    this.m = grid.length;
    this.n = grid[0].length;
    this.seq = 1;
	    
    int[] ans = new int[hits.length];
	    
    for (int i = 0; i < hits.length; ++i)
        ans[i] = hit(hits[i][1], hits[i][0]);   //hit函数返回击落对应celling后掉落砖块的数量
	    
    return ans;
}
	  
private int hit(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m || g[y][x] == 0) return 0;
    g[y][x] = 0;
    int ans = 0;  //击碎(x,y)引起的砖块掉落的数量
    for (int i = 0; i < 4; ++i) { //遍历与(x,y)相连的其他方向的砖块，判断是否会掉落
        ++seq;  //把同一连通分量全都标记为seq
	count = 0;
	if (!fall(x + dirs[i], y + dirs[i + 1], false)) continue;  //如果不掉落的话就continue，判断下一个方向的砖块  
	    ans += count;
	    ++seq; //注意此处seq++，从而不会与之前的seq重复，用于清除掉落的砖块
	    fall(x + dirs[i], y + dirs[i + 1], true);  //将要掉落的砖块清零
	}
    return ans;
}
	  
/*
 * Set all nodes in this CC(Connected Component) as seq_ or 0 if clear.
 * count: the # of nodes in this CC.
 */
private boolean fall(int x, int y, boolean clear) {
    if (x < 0 || x >= n || y < 0 || y >= m) return true;
    if (g[y][x] == seq || g[y][x] == 0) return true; //g[y][x]==seq代表之前已经遍历过，已经判断为掉落
    if (y == 0) return false;  //该砖块在第一层，不会掉落
    g[y][x] = clear ? 0 : seq; //变量clear用在hit第二次调用fall函数用来清除掉落砖块时使用
    ++count; //从目前的情况看该砖块是要掉落的，然而一旦在下面的fall函数调用过程中，有一个相连的砖块不掉落，会返回false，从而hit函数中不会添加该次遍历统计得到的count
    for (int i = 0; i < 4; ++i)
        if (!fall(x + dirs[i], y + dirs[i + 1], clear)) return false; //与其相连的一个砖块不掉落，则整个连通分量不掉落，返回false
    return true;
}
⚠️ **GitHub.com Fallback** ⚠️