LeetCode 最近每日一题出了好几道并查集的题，有几道挺有意思的，记录一下
Difficulty: 中等
n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi , yi ] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。
示例 1：
输入：stones = [[0 ,0 ],[0 ,1 ],[1 ,0 ],[1 ,2 ],[2 ,1 ],[2 ,2 ]] 输出：5 解释：一种移除 5 块石头的方法如下所示： 1. 移除石头 [2 ,2 ] ，因为它和 [2 ,1 ] 同行。2. 移除石头 [2 ,1 ] ，因为它和 [0 ,1 ] 同列。3. 移除石头 [1 ,2 ] ，因为它和 [1 ,0 ] 同行。4. 移除石头 [1 ,0 ] ，因为它和 [0 ,0 ] 同列。5. 移除石头 [0 ,1 ] ，因为它和 [0 ,0 ] 同行。石头 [0 ,0 ] 不能移除，因为它没有与另一块石头同行/列。
示例 2：
输入：stones = [[0 ,0 ],[0 ,2 ],[1 ,1 ],[2 ,0 ],[2 ,2 ]] 输出：3 解释：一种移除 3 块石头的方法如下所示： 1. 移除石头 [2 ,2 ] ，因为它和 [2 ,0 ] 同行。2. 移除石头 [2 ,0 ] ，因为它和 [0 ,0 ] 同列。3. 移除石头 [0 ,2 ] ，因为它和 [0 ,0 ] 同行。石头 [0 ,0 ] 和 [1 ,1 ] 不能移除，因为它们没有与另一块石头同行/列。
示例 3：
输入：stones = [[0 ,0 ]] 输出：0 解释：[0 ,0 ] 是平面上唯一一块石头，所以不可以移除它。
提示：
1 <= stones.length <= 1000
0 <= xi , yi <= 104
不会有两块石头放在同一个坐标点上
解法一 简单的想法肯定是直接双重循环枚举所有的点对，如果两个点横纵坐标有一样的就合并，最后统计下就行了，但是这样时间复杂度就比较高了。
这里我们换一个思路来合并，因为我们并不关心各个点是如何联通的，只要各个点在同一行或者同一列那么他们就是连通的，所以我们可以直接将每个点的行列坐标进行合并，也就相当于我们将 该行以及该列的所有元素 与 当前的元素 合并起来，最后用石头数量减去连通分量的个数就行了。需要注意的点就是我们需要区分横纵坐标，避免混淆。比如（1，2）和（2，4）不是同一行列，如果不加区分就会被合并成一个连通分量，这里题目给了行列的范围，我们直接加上一个 10001 就行了
class Solution (object ): def removeStones (self, stones: List [List [int ]] ) -> int : n = len (stones) parent = {} count = 0 def union (a, b ): nonlocal count pa = find(a) pb = find(b) if pa == pb: return count -= 1 parent[pa] = pb def find (a ): nonlocal count if a not in parent: count += 1 parent[a] = a return a if a == parent[a]: return a parent[a] = find(parent.get(a)) return parent.get(a) for s in stones: union(s[0 ]+10001 , s[1 ]) return n - count
Difficulty: 困难
有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定 （不会掉落）的前提是：
一块砖直接连接到网格的顶部，或者
至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。
返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。
注意 ，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。
示例 1：
输入：grid = [[1 ,0 ,0 ,0 ],[1 ,1 ,1 ,0 ]], hits = [[1 ,0 ]] 输出：[2 ] 解释： 网格开始为： [[1 ,0 ,0 ,0 ]， [1 ,1 ,1 ,0 ]] 消除 (1 ,0 ) 处加粗的砖块，得到网格： [[1 ,0 ,0 ,0 ] [0 ,1 ,1 ,0 ]] 两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格： [[1 ,0 ,0 ,0 ], [0 ,0 ,0 ,0 ]] 因此，结果为 [2 ] 。
示例 2：
输入：grid = [[1 ,0 ,0 ,0 ],[1 ,1 ,0 ,0 ]], hits = [[1 ,1 ],[1 ,0 ]] 输出：[0 ,0 ] 解释： 网格开始为： [[1 ,0 ,0 ,0 ], [1 ,1 ,0 ,0 ]] 消除 (1 ,1 ) 处加粗的砖块，得到网格： [[1 ,0 ,0 ,0 ], [1 ,0 ,0 ,0 ]] 剩下的砖都很稳定，所以不会掉落。网格保持不变： [[1 ,0 ,0 ,0 ], [1 ,0 ,0 ,0 ]] 接下来消除 (1 ,0 ) 处加粗的砖块，得到网格： [[1 ,0 ,0 ,0 ], [0 ,0 ,0 ,0 ]] 剩下的砖块仍然是稳定的，所以不会有砖块掉落。 因此，结果为 [0 ,0 ] 。
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] 为 0 或 1
1 <= hits.length <= 4 * 104
hits[i].length == 2
0 <= xi <= m - 1
0 <= yi <= n - 1
所有 (xi , yi ) 互不相同
解法一 也是一道很有意思的并查集的题。常规意义上的并查集只能处理连通块的合并，而这题打掉一个砖块意味着连通分量的拆分，那我们应该如何利用并查集呢？
这里的解法很巧妙的采用了 逆向思维 ，既然打掉砖块无法操作，那么我们可以反过来补砖块，先将原本待打击的地方置为 0，然后逆向的的补上去，而补的操作就代表着连通块的合并，我们就可以通过连通块数量的变化统计掉落的砖块，整体的思路非常巧妙。
具体的算法实现还是有一些细节需要注意，都注释在代码中了
import java.util.*;import java.io.*; class Solution { int [] parent; int [] size; public int find (int a) { if (parent[a] == a) return a; return parent[a] = find(parent[a]); } public void union (int a, int b) { int pa = find(a); int pb = find(b); if (pa == pb) return ; if (size[pa] > size[pb]) { parent[pb] = pa; size[pa] += size[pb]; } else { parent[pa] = pb; size[pb] += size[pa]; } } public int [] hitBricks(int [][] grid, int [][] hits) { int n = grid.length, m = grid[0 ].length; int hlen = hits.length; int [] exist = new int [hlen]; for (int i = 0 ; i < hlen; i++) { int x = hits[i][0 ], y = hits[i][1 ]; exist[i] = grid[x][y]&1 ; grid[x][y] = 0 ; } parent = new int [m*n+1 ]; size = new int [m*n+1 ]; int ROOT = m*n; for (int i = 0 ; i <= m*n; i++) { parent[i] = i; size[i] = 1 ; } for (int j = 0 ; j < m; j++) { if (grid[0 ][j] == 1 ) { union(ROOT, j); } } for (int i = 1 ; i < n; i++) { for (int j = 0 ; j < m; j++) { if (grid[i][j]==1 ) { if (j-1 >= 0 && grid[i][j-1 ] == 1 ) { union(m*i+j, m*i+j-1 ); } if ( grid[i-1 ][j] == 1 ) { union(m*i+j, m*(i-1 )+j); } } } } int [] res = new int [hlen]; int [] dir = {1 , 0 , -1 , 0 , 1 }; for (int i = hlen-1 ; i >= 0 ; i--) { int last = size[find(ROOT)]; int x = hits[i][0 ], y = hits[i][1 ]; grid[x][y] = exist[i]&1 ; if (grid[x][y] == 0 ) continue ; if (x == 0 ) union(ROOT, x*m+y); for (int k = 0 ; k < 4 ; k++) { int nx = x + dir[k], ny = y + dir[k+1 ]; if (nx < 0 || ny < 0 || nx >= n || ny >= m || grid[nx][ny] != 1 ) { continue ; } union(x*m+y, nx*m+ny); } res[i] = Math.max(0 , size[find(ROOT)]-last-1 ); } return res; } }
Difficulty: 中等
给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按字符 ASCII 顺序排列的邮箱地址。账户本身可以以任意顺序返回。
示例 1：
输入： accounts = [["John" , "johnsmith@mail.com" , "john00@mail.com" ], ["John" , "johnnybravo@mail.com" ], ["John" , "johnsmith@mail.com" , "john_newyork@mail.com" ], ["Mary" , "mary@mail.com" ]] 输出： [["John" , 'john00@mail.com' , 'john_newyork@mail.com' , 'johnsmith@mail.com' ], ["John" , "johnnybravo@mail.com" ], ["Mary" , "mary@mail.com" ]] 解释： 第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "johnsmith@mail.com" 。 第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。 可以以任何顺序返回这些列表，例如答案 [['Mary' ，'mary@mail.com' ]，['John' ，'johnnybravo@mail.com' ]， ['John' ，'john00@mail.com' ，'john_newyork@mail.com' ，'johnsmith@mail.com' ]] 也是正确的。
提示：
accounts的长度将在[1，1000]的范围内。
accounts[i]的长度将在[1，10]的范围内。
accounts[i][j]的长度将在[1，30]的范围内。
解法一
没错，这是第二道，上面的是第 0 道和第 1 道😁
本来不想记这道题的，没啥意思，业务题，但是写都写了，还是记一下，难倒是不难，就是要理清楚思路，我感觉很麻烦直接看了题解😂，不过题解也有点小瑕疵，邮件映射姓名的时候可以用邮件的编号直接映射的，题解依然用的字符串。这种题其实只想理清楚先干嘛后干嘛就好做了，别老想着一步都求出来，先分步，后面能合并再合并。
import java.util.*; import java.io.*;class Solution { int [] parent; public void union (int a, int b) { parent[find(a)] = find(b); } public int find (int a) { if (parent[a] == a) return a; return parent[a] = find(parent[a]); } public List<List<String>> accountsMerge (List<List<String>> acc) { HashMap<String, Integer> e2i = new HashMap <>(); HashMap<Integer, String> i2n = new HashMap <>(); int cnt = 0 ; for (int i = 0 ; i < acc.size(); i++) { String name = acc.get(i).get(0 ); for (int j = 1 ; j < acc.get(i).size(); j++) { String email = acc.get(i).get(j); if (!e2i.containsKey(email)) { e2i.put(email, cnt); i2n.put(cnt++, name); } } } parent = new int [cnt]; for (int i = 0 ; i < cnt; i++) { parent[i] = i; } for (int i = 0 ; i < acc.size(); i++) { int first = e2i.get(acc.get(i).get(1 )); for (int j = 2 ; j < acc.get(i).size(); j++) { union(first, e2i.get(acc.get(i).get(j))); } } HashMap<Integer, List<String>> map = new HashMap <>(); for (String email : e2i.keySet()) { map.computeIfAbsent(find(e2i.get(email)), k->new LinkedList <>()).add(email); } List<List<String>> res = new ArrayList <>(); for (Integer idx : map.keySet()) { String name = i2n.get(idx); List<String> emails = map.get(idx); Collections.sort(emails); emails.add(0 , name); res.add(emails); } return res; } }
