Re: [閒聊] 每日leetcode

看板Marginalman作者dont (dont)時間1年前 (2024/08/29 13:58)推噓3(3推 0噓 0→)

留言3則, 3人參與討論串781/1553 (看更多)

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