0947. 移除最多的同行或同列石头

0947. 移除最多的同行或同列石头 #

  • 标签:深度优先搜索、并查集、图
  • 难度:中等

题目大意 #

二维平面中有 n 块石头,每块石头都在整数坐标点上,且每个坐标点上最多只能有一块石头。

如果一块石头的同行或者同列上有其他石头存在,那么就可以移除这块石头。

给你一个长度为 n 的数组 stones ,其中 stones[i] = [xi, yi] 表示第 i 块石头的位置,返回可以移除的石子的最大数量。

解题思路 #

只要横向和纵向上有石头连在一起,只保留一个石头即可。

可以构建一个无向图,只要两个石头同行或者同列,就将两个点相连接。

利用并查集,将石头的横纵坐标加入到一个集合中,这样同行、同列的石头都在一个集合中了。然后计算出图的连通分量个数。

则答案为:可以移除石子的最大数量 = 所有石头个数 - 连通分量个数。

因为石子坐标是二维的,在使用并查集的时候要区分横纵坐标,因为 $0 <= xi, yi <= 10^4$,可以取 n = 10010,将纵坐标映射到 [n, n + 10000] 的范围内,这样就可以得到所有节点的标号。

最后计算集合个数,可以使用 set 集合去重,然后统计数量。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.count = n

    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return

        self.parent[root_x] = root_y
        self.count -= 1

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        size = len(stones)
        n = 10010
        union_find = UnionFind(n * 2)
        for i in range(size):
            union_find.union(stones[i][0], stones[i][1] + n)

        stones_set = set()
        for i in range(size):
            stones_set.add(union_find.find(stones[i][0]))

        return size - len(stones_set)
本站总访问量  次  |  您是本站第  位访问者