Re: [閒聊] 每日leetcode

[dont (dont)]

947. Most Stones Removed with Same Row or Column

## 思路

stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]

分成兩個group:

[0,0], [0,2], [2,0], [2,2] -> 刪掉3個stone
[1,1]

所以用UnionFind

用兩個dict 記錄每個row跟col最後看到的石頭idx

如果在同一條線上已經有石頭了, 就作union

## Complexity

Time: O(N a(N))
Space: O(N)

## Code

```python
class UnionFind:
    def __init__(self, n):
        self.root = list(range(n))
        self.rank = [1] * n

    def find(self, x):
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return 0
        if self.rank[rx] >= self.rank[ry]:
            self.rank[rx] += self.rank[ry]
            self.root[ry] = rx
        else:
            self.rank[ry] += self.rank[rx]
            self.root[rx] = ry
        return 1


class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n = len(stones)
        uf = UnionFind(n)

        seen_rows = defaultdict(int)  # row -> idx
        seen_cols = defaultdict(int)  # col -> idx

        res = 0
        for idx, (r, c) in enumerate(stones):
            if r in seen_rows:
                res += uf.union(seen_rows[r], idx)
            if c in seen_cols:
                res += uf.union(seen_cols[c], idx)
            seen_rows[r] = idx
            seen_cols[c] = idx

        return res
```

--
http://i.imgur.com/OLvBn3b.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.17 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724911123.A.D9F.html
推 sustainer123: 大師
推 argorok: 大師
推 oin1104: 大師
※ 編輯: dont (185.213.82.17 臺灣), 08/29/2024 14:13:03