文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载本篇题解围绕 LeetCode 947「移除最多的同行或同列石头」展开讲解如何把「同行 / 同列可互相移除」的规则抽象为联通分量问题并给出基础并查集、优化并查集与 DFS 三种完整可运行解法及其复杂度分析。读完本文你将掌握「连通性」类题目的通用建模思路并查集计数联通分量、坐标偏移映射、懒初始化等技巧并能直接套用于仓库 并查集专题 与 小岛问题专题 中的同类题目。题目描述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 10000 xi, yi 10^4不会有两块石头放在同一个坐标点上前置知识并查集Union-Find思路分析读完题目后观察数据范围n 最大 1000可以猜测时间复杂度大约在 $O(n^2)$ 量级。进一步分析示例会发现题目描述的「同行 / 同列可互相移除」本质上是一种联通关系——一块石头不仅能移除与它直接同行同列的石头还能通过「邻居的邻居」一路传导下去。这类「行和列具有某种绑定关系」的题目正是并查集的典型应用场景核心目标就是求联通区域的个数。把问题抽象为联通分量将每块石头看作图中的一个节点若两块石头同行或同列则在二者之间连一条边。这样所有石头会被划分成若干联通分量连通子图。可以证明一个联通分量内最多只能剩下 1 块石头其余都可以被移除。因此答案为答案 n - 联通分量的个数其中 n 为 stones 的长度。例如示例 1 的 6 块石头全部连成一个联通分量故答案是6 - 1 5示例 2 的 5 块石头分为两个联通分量[0,0],[0,2],[2,0],[2,2]一组、[1,1]单独一组故答案是5 - 2 3。为什么一个联通分量能且只能剩一块石头「能」的论证使用 DFS / BFS 遍历一个联通分量访问顺序本身对应一条「有效移除序列」。因为每次访问到的节点在访问时必然与已访问节点同行或同列正是通过这条边到达的所以访问路径的逆序或有序 visited 记录的逆序就是一个可行的移除顺序最终只留下遍历的起点。这个论证同样说明 DFS / BFS 可以求解本题若题目进一步要求输出移除顺序用 DFS 记录路径即可。「只能」的论证若一个联通分量内剩余 2 块及以上石头则移除动作意味着最后留下的石头必须与某块被移除的石头同行或同列这与「联通分量」的闭合性矛盾——被移除石头的同行同列关系必然把残留石头连回该分量。因此每分量最多留 1 块答案即n - 联通分量数。并查集解题主线基础版将 n 块石头两两合并合并条件为「行相同或列相同」最后统计联通分量个数uf.cnt。优化版不再以石头为节点而是把横坐标、纵坐标分别作为节点用偏移量区分二者每块石头只需一次union联通分量个数在find过程中惰性统计。DFS / BFS 版把行、列映射为图的顶点建图然后统计联通分量个数。解法一基础并查集两两合并石头并查集模板回顾本题所用的class UF是仓库 并查集专题 中的标准无权并查集模板。其核心 API 如下find(x)返回 x 所在集合的代表根。递归实现中同时完成路径压缩把查找路径上的节点直接挂到根上将树高压低避免 find 退化为 $O(n)$union(p, q)若 p、q 不联通则将其中一个根挂到另一个根上并使联通分量计数cnt减 1connected(p, q)判断 p、q 是否联通即find(p) find(q)。仓库模板中还展示了带size的按秩按大小合并总是把较小的树挂到较大的树上使树尽量平衡配合路径压缩后单次操作复杂度趋近 $O(1)$严格说是阿克曼函数反函数量级。本题两两合并写法省去按秩合并以突出主脉络两者均正确。代码Python3class UF: def __init__(self, M): self.parent {} self.cnt 0 # 初始化 parent 和 cnt for i in range(M): self.parent[i] i self.cnt 1 def find(self, x): if x ! self.parent[x]: self.parent[x] self.find(self.parent[x]) return self.parent[x] return x def union(self, p, q): if self.connected(p, q): return leader_p self.find(p) leader_q self.find(q) self.parent[leader_p] leader_q self.cnt - 1 def connected(self, p, q): return self.find(p) self.find(q) class Solution: def removeStones(self, stones: List[List[int]]) - int: n len(stones) uf UF(n) # 两个 for 循环将石头两两合并 for i in range(n): for j in range(i 1, n): # 如果行或者列相同将其联通成一个子图 if stones[i][0] stones[j][0] or stones[i][1] stones[j][1]: uf.union(i, j) return n - uf.cnt初始化时每个石头各自为一个联通分量cnt n每次合并使cnt减 1最终n - uf.cnt即最多可移除数量。复杂度分析令 n 为数组 stones 的长度时间复杂度$O(n^2 \log n)$两两枚举 $O(n^2)$ 次每次 union/find 受路径压缩影响近似 $O(\log n)$ 以内空间复杂度$O(n)$parent 哈希表存储 n 个节点。解法二优化并查集坐标映射 懒初始化优化动机解法一将「石头」作为联通节点需要两两枚举复杂度为 $O(n^2)$。实际上横坐标相同或纵坐标相同才是联通条件因此可以反过来把横坐标、纵坐标分别作为节点横坐标相同的石头共享一个「行节点」纵坐标相同的共享一个「列节点」每块石头只需把它的行节点与列节点合并一次即可把所有同行同列的石头串进同一联通分量。用偏移量区分横纵坐标由于题目限定横纵坐标取值在0 xi, yi 10^4含 10000行节点与列节点的取值范围存在重叠都是 0~10000。为区分二者将横坐标统一加上偏移量10001即大于坐标上限 10001 即可保证x 10001永不与任何y值冲突于是每个节点编号唯一行节点编号x 10001列节点编号y例如石头[0, 0]即合并节点10001与0。懒初始化的 find优化版中不能像基础版那样在构造时预先统计联通分量数因为横、纵坐标的不重复个数事先未知。解决方式是在 find 过程中惰性创建节点当x尚未出现在 parent 中时令parent[x] x并让cnt 1随后正常走路径压缩union 合并成功时cnt - 1。这样一遍union循环即可完成全部统计实现 one-pass。代码Python3class UF: def __init__(self, M): self.parent {} self.cnt 0 def find(self, x): if x not in self.parent: self.cnt 1 self.parent[x] x if x ! self.parent[x]: self.parent[x] self.find(self.parent[x]) return self.parent[x] return x def union(self, p, q): if self.connected(p, q): return leader_p self.find(p) leader_q self.find(q) self.parent[leader_p] leader_q self.cnt - 1 def connected(self, p, q): return self.find(p) self.find(q) class Solution: def removeStones(self, stones: List[List[int]]) - int: n len(stones) uf UF(0) for i in range(n): uf.union(stones[i][0] 10001, stones[i][1]) return n - uf.cnt注意这里的cnt统计的是「横纵坐标联通分量」的个数。为什么n - uf.cnt仍是答案因为每块石头把它的行节点与列节点连在一起每个石头联通分量恰对应一个「行/列互达」的联通块其内石头数量减 1 即为可移除数累加所有联通块即n - uf.cnt。这与解法一的结论一致。复杂度分析令 n 为数组 stones 的长度时间复杂度$O(n \log n)$只需一次遍历每次 union 近似 $O(\log n)$ 以内配合路径压缩趋近常数空间复杂度$O(n)$parent 哈希表最多存储 2n 量级的节点即每块石头贡献一个行节点和一个列节点。解法三DFS 遍历联通分量Java除了并查集本题也可用 DFS / BFS 求解思路与仓库 小岛问题专题 一脉相承从每个未访问节点出发遍历整个联通分量计数加一。由于本题的「相邻」关系定义在行、列上需要把行、列号映射为图的顶点x - 10000表示行顶点y表示列顶点每块石头作为一条连接行顶点与列顶点的边建图完成后统计联通分量个数即可。代码Javapublic int removeStones(int[][] stones) { Set visit new HashSet(); int count 0; int offset 10000; HashMapInteger, Listint[] map new HashMap(); // 构造图行/列作为图的顶点每块石头连接其行顶点与列顶点 for (int i 0; i stones.length; i) { int[] node stones[i]; Listint[] list map.getOrDefault(node[0] - offset, new ArrayList()); list.add(node); map.put(node[0] - offset, list); Listint[] list1 map.getOrDefault(node[1], new ArrayList()); list1.add(node); map.put(node[1], list1); } // 寻找联通分量 for (int i 0; i stones.length; i) { int[] node stones[i]; if (!visit.contains((node))) { visit.add((node)); dfs(node, visit, map); count; } } return stones.length - count; } // 遍历节点 public void dfs(int[] node, Set set, HashMapInteger, Listint[] map) { int offset 10000; Listint[] list map.getOrDefault(node[0] - offset, new ArrayList()); for (int i 0; i list.size(); i) { int[] item list.get(i); if (!set.contains((item))) { set.add((item)); dfs(item, set, map); } } Listint[] list2 map.getOrDefault(node[1], new ArrayList()); for (int i 0; i list2.size(); i) { int[] item list2.get(i); if (!set.contains((item))) { set.add((item)); dfs(item, set, map); } } }复杂度分析令 n 为数组 stones 的长度时间复杂度建图与遍历图的时间均为 $O(n)$空间复杂度$O(n)$邻接表存储所有石头节点。三种解法对比解法建模方式时间复杂度空间复杂度适用场景基础并查集石头两两合并合并条件为同行/同列$O(n^2 \log n)$$O(n)$n 较小、思路最直白优化并查集横/纵坐标分别作为节点偏移量区分懒初始化$O(n \log n)$$O(n)$n 较大时的首选DFSBFS行/列为顶点建图统计联通分量$O(n)$$O(n)$需要进一步输出移除顺序时可扩展记录路径三种解法的正确性都建立在同一数学结论之上答案 n − 联通分量个数。并查集通过「合并」隐式维护联通分量DFS/BFS 通过「遍历」显式划分联通分量殊途同归。与仓库其他题目的联系本题是「连通性」类题目的代表性应用可与仓库中以下内容对照练习并查集专题union-find含背景、核心 API、路径压缩、按秩合并、带权并查集模板与复杂度分析是本题模板的出处小岛问题专题islandDFS / BFS 求联通分量的通用套路与模板可配合本题解法三练习同属「求联通分量个数」的并查集题目547. 省份数量、839. 相似字符串组、959. 由斜杠切分区域并查集其他应用721. 账户合并等价类合并、5936. 引爆最多的炸弹联通分量计数、3108. 带权图最小代价行走带权联通性、1168. 水资源分配优化并查集 最小生成树思想、1697. 检查边长度限制的路径是否存在离线 并查集。总结解 LeetCode 947 的关键在于识别题目背后的联通关系同行 / 同列的石头构成联通分量每分量最多保留一块石头答案即n − 联通分量数。实现上基础并查集思路直观优化版通过「坐标 偏移量映射 懒初始化 find」把复杂度从 $O(n^2 \log n)$ 降到 $O(n \log n)$是面试中值得重点掌握的进阶写法DFS / BFS 版本则在需要输出移除顺序的场景下更具扩展性。遇到「连通、等价、互相可达」类题目时优先联想并查集并注意使用路径压缩必要时空闲时配合按秩合并可显著降低出错率与运行时间。赞分享文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载相关推荐LeetCode-Go 题解947. Most Stones Removed with Same Row or Column——并查集建模与行列映射优化实战LeetCode Go 题解947. Most Stones Removed with Same Row or Column——并查集建模与行列映射优化实战示例工程LeetCode 1579 题解并查集删除最多边保持图完全可遍历LeetCode-Go 实现LeetCode 1579 题解并查集删除最多边保持图完全可遍历LeetCode Go 实现 本篇技术指南以 LeetCode 第 1579 题《Remo示例工程LeetCode 721. Accounts Merge 并查集解法详解用 Go 合并同一用户的邮箱账户LeetCode 721. Accounts Merge 并查集解法详解用 Go 合并同一用户的邮箱账户 本文围绕 LeetCode 721 题《Accoun示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考