移除最多的同行或同列石头 图解题解

这道题到底在问什么

输入

stones=[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]

输出

5(6 颗石头连成 1 组,留 1 移 5)

最优解：一步一步想明白

1. 3记住「行列当节点 → 每颗石头 union 它的行和列 → 答案 = 石头数 − 连通块数」,下面逐帧套它。
2. 4先为用到的行、列各放一个节点:上排是第 0、1、2 行(R0、R1、R2),下排是第 0、1、2 列(C0、C1、C2)。此刻它们彼此独立,连通块数 = 6,相当于行列还没被任何石头牵连。
3. 5并查集准备就绪:每个行/列节点的 parent 先指向自己。接下来按顺序扫每颗石头,把它的行节点和列节点并起来。
4. 6第 1 颗石头 (0, 0):它占住第 0 行和第 0 列,所以要把行节点 R0 和列节点 C0 连起来(它俩高亮)。
5. 7union(R0, C0):各自 find 出根后,把 R0 那组的根接到 C0 所在组的根上(union 永远是接到对方的根、不是接到某个普通节点),两组并成同一个连通块(同色)。连通块数减 1,现在是 5。
6. 8第 2 颗石头 (0, 1):它占住第 0 行和第 1 列,所以要把行节点 R0 和列节点 C1 连起来(它俩高亮)。
7. 9union(R0, C1):各自 find 出根后,把 R0 那组的根接到 C1 所在组的根上(union 永远是接到对方的根、不是接到某个普通节点),两组并成同一个连通块(同色)。连通块数减 1,现在是 4。
8. 10第 3 颗石头 (1, 0):它占住第 1 行和第 0 列,所以要把行节点 R1 和列节点 C0 连起来(它俩高亮)。
9. 11union(R1, C0):各自 find 出根后,把 R1 那组的根接到 C0 所在组的根上(union 永远是接到对方的根、不是接到某个普通节点),两组并成同一个连通块(同色)。连通块数减 1,现在是 3。
10. 12第 4 颗石头 (1, 2):它占住第 1 行和第 2 列,所以要把行节点 R1 和列节点 C2 连起来(它俩高亮)。
11. 13union(R1, C2):各自 find 出根后,把 R1 那组的根接到 C2 所在组的根上(union 永远是接到对方的根、不是接到某个普通节点),两组并成同一个连通块(同色)。连通块数减 1,现在是 2。
12. 14第 5 颗石头 (2, 1):它占住第 2 行和第 1 列,所以要把行节点 R2 和列节点 C1 连起来(它俩高亮)。
13. 15union(R2, C1):各自 find 出根后,把 R2 那组的根接到 C1 所在组的根上(union 永远是接到对方的根、不是接到某个普通节点),两组并成同一个连通块(同色)。连通块数减 1,现在是 1。
14. 16第 6 颗石头 (2, 2):它占住第 2 行和第 2 列,所以要把行节点 R2 和列节点 C2 连起来(它俩高亮)。
15. 17union(R2, C2):先各自 find 根,发现 R2 和 C2 已经在同一个连通块里了(被前面的石头经别的行列间接连通过)。这一步是个环、不改变结构,连通块数仍是 1。
16. 18六颗石头都扫完了。看整张图:R0、R1、R2、C0、C1、C2 六个行列节点经一连串 union 全连到了一起,只剩 1 个连通块,说明这 6 颗石头其实是「互相牵连」的一大堆。
17. 19数连通块的办法:对每个节点做一次 find 拿到它的根,根相同的就是同一块。下面逐个看,看它们是不是都指向同一个根。
18. 20find(R0) 的根是 C2。这是目前见到的第 1 个不同的根。
19. 21find(R1) 的根是 C2。和前面某个节点的根相同,归入同一连通块,不新增。
20. 22find(R2) 的根是 C2。和前面某个节点的根相同,归入同一连通块,不新增。
21. 23find(C0) 的根是 C2。和前面某个节点的根相同,归入同一连通块,不新增。
22. 24find(C1) 的根是 C2。和前面某个节点的根相同,归入同一连通块,不新增。
23. 25find(C2) 的根是 C2。和前面某个节点的根相同,归入同一连通块,不新增。
24. 26数下来只有 1 个不同的根,也就是 1 个连通块。每个连通块里的石头互相同行或同列连着,可以一颗颗移到只剩 1 颗。所以最多移除 = 石头数 − 连通块数 = 6 − 1 = 5。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        parent = {}
        def find(x):
            parent.setdefault(x, x)
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        for r, c in stones:
            parent[find(('r', r))] = find(('c', c))
        roots = {find(('r', r)) for r, _ in stones}
        return len(stones) - len(roots)

#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
    unordered_map<int,int> parent;
    int find(int x) {
        if (!parent.count(x)) parent[x] = x;
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
public:
    int removeStones(vector<vector<int>>& stones) {
        parent.clear();
        const int OFFSET = 10001;
        for (auto &s : stones) parent[find(s[0])] = find(s[1] + OFFSET);
        unordered_set<int> roots;
        for (auto &s : stones) roots.insert(find(s[0]));
        return stones.size() - roots.size();
    }
};

import java.util.*;
class Solution {
    Map<Integer, Integer> parent = new HashMap<>();
    public int removeStones(int[][] stones) {
        parent.clear();
        int offset = 10001;
        for (int[] s : stones) parent.put(find(s[0]), find(s[1] + offset));
        Set<Integer> roots = new HashSet<>();
        for (int[] s : stones) roots.add(find(s[0]));
        return stones.length - roots.size();
    }
    private int find(int x) {
        parent.putIfAbsent(x, x);
        if (!parent.get(x).equals(x)) parent.put(x, find(parent.get(x)));
        return parent.get(x);
    }
}

复杂度

面试官可能追问