Tadowの自留地
文章 标签 分类 关于 SelfHost
Tadowの自留地

目录

记两道并查集的题（lc947 & lc803）

reso1mi 收录于 算法
   约 3121 字   预计阅读 7 分钟 

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] 为 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;
        //记录当前 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;
    }
}
更新于 2021-01-18
 算法
返回 | 主页