↓Skip to main content
  1. Posts/

LeetCode-947 移除最多的同行或同列石头

·1 min·
Table of Contents

LeetCode-947 移除最多的同行或同列石头 #

Solution 1 #

把石头看成点, 同行或同列的石头连一条边, 那么一个大小为 $m$ 的联通分量可以移除 $m - 1$ 个节点. 可以用 DFS 来寻找联通分量.

代码如下:

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n = len(stones)
        g = [[] for _ in range(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]:
                    g[i].append(j)
                    g[j].append(i)
        
        vis = [False] * n   

        def f(i):
            vis[i] = True 
            for j in g[i]:
                if not vis[j]:
                    f(j)
            return

        ans = 0
        for i in range(n):
            if not vis[i]:
                f(i)
                ans += 1
        return n - ans

Solution 2 #

并查集.

代码如下:

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        parent = {}
        
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]] 
                x = parent[x]
            return x
        
        def union(x, y):
            parent.setdefault(x, x)
            parent.setdefault(y, y)
            parent[find(x)] = find(y)
        
        for x, y in stones: 
            union(x, ~y) # 用 ~y 区分行和列, x 行和 y 列的先合并到一个联通分量中
        
        roots = set()
        for x, y in stones:
            roots.add(find(x))
        
        return len(stones) - len(roots)