LeetCode最近每日一题出了好几道并查集的题,有几道挺有意思的,记录一下

947. 移除最多的同行或同列石头

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

803. 打砖块

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] 为 01
  • 1 <= hits.length <= 4 * 104
  • hits[i].length == 2
  • 0 <= x<= 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;
//记录当前hits对应的位置有没有砖块
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 (/*i-1 >= 0 &&*/ 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];
//WA_2: 还原错误,hit原本可能没有砖块,一开始直接还原成1了
grid[x][y] = exist[i]&1;
if (grid[x][y] == 0) continue;
//WA_1: 还原后和ROOT连接的别忘了合并
if (x == 0) union(ROOT, x*m+y);
//与周围4个方向的方块合并
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;
}
}

721. 账户合并

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) {
//email : idx
HashMap<String, Integer> e2i = new HashMap<>();
//idx : name
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)));
}
}
// idx : emails
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;
}
}