- [数据结构总览](./thinkings/basic-data-structure.md)

- [链表专题](./thinkings/linked-list.md) 🆕

- [树专题](./thinkings/tree.md) 🆕

- [堆专题（上）](./thinkings/heap.md) 🆕

- [二叉树的遍历](./thinkings/binary-tree-traversal.md)

- [动态规划](./thinkings/dynamic-programming.md)

- [回溯](./thinkings/backtrack.md)

- [哈夫曼编码和游程编码](./thinkings/run-length-encode-and-huffman-encode.md)

- [布隆过滤器](./thinkings/bloom-filter.md)🖊

- [字符串问题](./thinkings/string-problems.md)

- [前缀树](./thinkings/trie.md)🖊

- [《日程安排》专题](https://lucifer.ren/blog/2020/02/03/leetcode-%E6%88%91%E7%9A%84%E6%97%A5%E7%A8%8B%E5%AE%89%E6%8E%92%E8%A1%A8%E7%B3%BB%E5%88%97/)

- [《构造二叉树》专题](https://lucifer.ren/blog/2020/02/08/%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%93%E9%A2%98/)

- [《贪婪策略》专题](./thinkings/greedy.md)

- [深度优先遍历](./thinkings/DFS.md)

- [滑动窗口（思路 + 模板）](./thinkings/slide-window.md)

- [位运算](./thinkings/bit.md)

- [设计题](./thinkings/design.md)

- [小岛问题](./thinkings/island.md)🖊

- [最大公约数](./thinkings/GCD.md)

- [并查集](./thinkings/union-find.md)

- [平衡二叉树专题](./thinkings/balanced-tree.md)

- [蓄水池抽样](./thinkings/reservoid-sampling.md) 🆕

- [单调栈](./thinkings/monotone-stack.md) 🆕

- [字典序列删除](./selected/a-deleted.md)

- [一次搞定前缀和](./selected/atMostK.md)

- [字节跳动的算法面试题是什么难度？](./selected/byte-dance-algo-ex.md)

- [字节跳动的算法面试题是什么难度？（第二弹）](./selected/byte-dance-algo-ex-2017.md)

- [《我是你的妈妈呀》 - 第一期](./selected/mother-01.md)

- [一文带你看懂二叉树的序列化](./selected/serialize.md)

- [穿上衣服我就不认识你了？来聊聊最长上升子序列](./selected/LIS.md)

- [你的衣服我扒了 - 《最长公共子序列》](./selected/LCS.md)

- [一文看懂《最大子序列和问题》](./selected/LSS.md)

- [0947. 移除最多的同行或同列石头](./problems/947.most-stones-removed-with-same-row-or-column.md) 🆕

* [0947. 移除最多的同行或同列石头](./problems/947.most-stones-removed-with-same-row-or-column.md) 🆕

- [并查集](https://github.com/azl397985856/leetcode/blob/master/thinkings/union-find.md)

读完题目之后， 看了下数据范围。我猜测可能和动态规划什么的有关，**而且时间复杂度是 $O(n^2)$ 左右**，其中 n 为 stones 的长度。继续看了下示例，然后跟着思考了一下，发现很像是某种联通关系。 类似的题目有很多，题目描述记不太清楚了。大概意思是给你一个二维网格，行和列需要**一起增加**，求最小和什么的。这类题目都是行和列具有某种绑定关系。 于是我想到了使用并查集来做。 后面想了一下，反正就是**求联通区域的个数**，因此使用 DFS 和 BFS 都可以。如果你想使用 DFS 或者 BFS 来解，可以结合我之前写的 [小岛专题](https://github.com/azl397985856/leetcode/blob/master/thinkings/island.md) 练习一下哦。

继续分析下题目。 题目的意思是任意一个石头可以消除和它同行和同列的其他石子。于是我就想象出了下面这样一幅图，其中红色的方块表示石子，方块的连线表示离得最近的可以消除的石子。实际上，一个石子除了可以消除图中线条直接相连的石子，还可以消除邻居的邻居。**这提示我们使用并查集维护这种联通关系**，联通的依据自然就是列或者行一样。

上面是一个全联通的图。如下是有两个联通域的图。

有了上面的知识，其实就可以将石子全部建立并查集的联系，并计算联通子图的个数。答案就是 n - 联通子图的个数，其中 n 为 stones 的长度。

核心代码：

n = len(stones)

uf = UF(n)

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

有的人想问，这可行么？即**我可以将一个联通子图的石子移除只剩下一个么？**

答案是肯定的。其实上面我提到了这道题也可使用 DFS 和 BFS 的方式来做。如果你使用 DFS 的方式来做，会发现其实 **DFS 路径的取反就是消除的顺序**，当然消除的顺序不唯一，因为遍历访问联通子图的序列并不唯一。 如果题目要求我们求移除顺序，那我们可以考虑使用 DFS 来做，同时记录路径信息即可。

使用遍历的方式（BFS 或者 DFS），由于每次访问一个石子都需要使用 visited 来记录访问信息防止环的产生，因此 visited 的逆序也是一个可行的移除顺序。不过这要求你的 visited 的是有序的。实现的方法有很多，有点偏题了，这里就不赘述了。

实际上，上面的并查集代码仍然可以优化。上面的思路是直接将点作为并查集的联通条件。实际上，我们可以将点的横纵坐标分别作为联通条件。即如果横坐标相同的联通到一个子图，纵坐标相同的联通到一个子图。如下图：

为了达到这个模板，我们不能再初始化的时候计算联通域数量了，即不能像上面那样 `uf = UF(n)`（此时联通域个数为 n）。因为横坐标，纵坐标分别有多少不重复的我们是不知道的，一种思路是先计算出**横坐标，纵坐标分别有多少不重复的**。这当然可以，还有一种思路是在 find 过程中计算，这样 one pass 即可完成，具体见下方代码区。

由于我们需要**区分横纵坐标**（上面图也可以看出来），因此可**用一种映射**区分二者。由于题目限定了横纵坐标取值为 10000 以内（包含 10000），一种思路就是将 x 或者 y 加上 10001。

核心代码：

n = len(stones)

uf = UF(0)

for i in range(n):

uf.union(stones[i][0] + 10001, stones[i][1])

return n - uf.cnt

代码支持： Python3

其中 `class UF` 部分是标准的无权并查集模板，我一行代码都没变。关于模板可以去 [并查集](https://github.com/azl397985856/leetcode/blob/master/thinkings/union-find.md) 查看。

class UF:

def __init__(self, M):

self.parent = {}

self.cnt = 0

# 初始化 parent，size 和 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 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

**复杂度分析**

令 n 为数组 stones 的长度。

- 时间复杂度：$O(n^2logn)$

- 空间复杂度：$O(n)$

代码支持： Python3

class 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

**复杂度分析**

令 n 为数组 stones 的长度。

- 时间复杂度：$O(nlogn)$

- 空间复杂度：$O(n)$

代码支持： Java

public int removeStones(int[][] stones) {

Set visit = new HashSet();

int count = 0;

int offset = 10000;

HashMap <Integer,List<int []>>map = new HashMap();

// 构造图 每一项是一个节点

for (int i = 0; i < stones.length; i++) {

int [] node = stones[i];

List<int []> list = map.getOrDefault(node[0]-offset,new ArrayList<>());

list.add(node);

map.put(node[0]-offset,list);

List<int []> 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,HashMap <Integer,List<int []>>map){

int offset = 10000;

List<int []> 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);

}

}

List<int []> 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)$

力扣的小伙伴的点下我头像的关注按钮，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 38K star 啦。