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; } }