难度：★★★☆☆
类型：图
方法：深度优先搜素，并查集
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。
示例 1：
输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5
解释：一种移除 5 块石头的方法如下所示：
- 移除石头 [2,2] ，因为它和 [2,1] 同行。
- 移除石头 [2,1] ，因为它和 [0,1] 同列。
- 移除石头 [1,2] ，因为它和 [1,0] 同行。
- 移除石头 [1,0] ，因为它和 [0,0] 同列。
- 移除石头 [0,1] ，因为它和 [0,0] 同行。
石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。
示例 2：
输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
解释：一种移除 3 块石头的方法如下所示：
- 移除石头 [2,2] ，因为它和 [2,0] 同行。
- 移除石头 [2,0] ，因为它和 [0,0] 同列。
- 移除石头 [0,2] ，因为它和 [0,0] 同行。
石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。
示例 3：
输入：stones = [[0,0]]
输出：0
解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。
提示：
1 <= stones.length <= 1000
0 <= xi, yi <= 104
不会有两块石头放在同一个坐标点上
解答
基于对问题的分析，有下面的一些定义需要留意：
第一，连接的定义。如果两个石头在同一行或者同一列，我们就说这两个石头是相互连接的；
第二，连接的传递性。如果石头A和石头B存在连接关系，且石头B和石头C存在连接关系，则石头A和石头C存在连接关系。
第三，连通域。我们把存在连接关系的若干结点组成的集合叫做一个连通域。（换言之，对于连通域中的所有石头，我们总可以通过调整移除石头的顺序，实现最后只剩下一块石头，这是本题的题眼）。
第四，问题的定义。我们把石头看做一个个结点，根据石头之间的连接关系可以构建出一张图，这道题实际上就是一个图的搜索问题。问题就是统计图中连通域的个数。
常用的是深度优先搜索或并查集算法。
方法1：深度优先搜索
深度优先搜索通过代码上的递归或栈实现逻辑上的连通域搜寻。
【建图】
我们给每个石头按照下标编号，然后使用一个字典来存储每个石头连接的石头的编号。例如对于石头i，其对应的值是由石头i所有存在连接关系的石头组成的列表。
【搜索】
使用递归方式实现搜索。需要注意的是，在搜索之前，先使用vis集合存储已经被查看过的石头，每次遍历到某个石头，则将该石头放进vis中。
【统计】
从第一个石头开始遍历，将各个石头所在连通域中所有石头放进集合，每次遍历到新的连通域，计数器num加一。需要注意跳过已经被查看过的石头。
【返回值】
最后返回石头总数n减去连通域的个数num。
from collections import defaultdict
class Solution:
def removeStones(self, stones):
n = len(stones)
graph = defaultdict(set)
for i, (x1, y1) in enumerate(stones):
for j, (x2, y2) in enumerate(stones):
if i != j and (x1 == x2 or y1 == y2):
graph[i].add(j)
graph[j].add(i)
def dfs(i):
vis.add(i)
for y in graph[i]:
if y not in vis:
dfs(y)
vis = set()
num = 0
for i in range(n):
if i not in vis:
num += 1
dfs(i)
return n - num
方法2：并查集
并查集的功能在于，将同一个连通域中的所有结点挂在同一根节点下，对于快速统计连通域的数目是非常方便的。
并查集包含几个主要方法：
【初始化】
一般情况下，并查集以哈希表的形式存在（列表由于索引关系的存在，本质也是哈希表），表达的是每个结点与其根节点的对应关系。初始情况下，将每个结点的根节点初始化为本身。
【连通域的合并】
将两个连通域合并成为一个大连通域，可以选取两个连通域中各自任意两个结点，将它们的根节点建立连接即可。
【查找根节点】
通过递归调用的方法可以找到根节点，在遍历过程中，将子节点的父节点改成根节点，大大减少计算开销。
为了便于理解，我们先把石头而非石头的坐标作为对象来研究。
我们将石头两两研究，如果存在连接关系，则将这两个石头所在连通域合并。最后通过统计根节点的数目来反映连通域的数目。
class UFS:
def __init__(self, stones):
self.dct = {stone: stone for stone in stones}
def find(self, stone):
if self.dct[stone] != stone:
self.dct[stone] = self.find(self.dct[stone])
return self.dct[stone]
def union(self, stone_1, stone_2):
root_1 = self.find(stone_1)
root_2 = self.find(stone_2)
self.dct[root_1] = root_2
class Solution(object):
def removeStones(self, stones):
stones = list(map(tuple, stones))
ufs = UFS(stones)
def same_row_or_column(stone_1, stone_2):
(x1, y1), (x2, y2) = stone_1, stone_2
return x1 == x2 or y1 == y2
for stone_1 in stones:
for stone_2 in stones:
if same_row_or_column(stone_1, stone_2):
ufs.union(stone_1, stone_2)
return len(stones) - len({ufs.find(stone) for stone in stones})
还有一种方法，即将石头位置的横纵坐标降维，合并到一个列表中，为了使得他们不干扰，纵坐标从10000开始计数（因为横坐标的最大值是10000）。这样做的好处是，省去了判断两个石头是否连接的过程，因为在并查集的内部就已经做了判断。
class UFS:
def __init__(self):
self.p = []
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, x, y):
xr = self.find(x)
yr = self.find(y)
self.p[xr] = yr
class Solution(object):
def removeStones(self, stones):
ufs = UFS()
for x, y in stones:
ufs.union(x, y + 10000)
return len(stones) - len({ufs.find(x) for x, y in stones})
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
网友评论