Re: [閒聊] 每日leetcode

看板Marginalman作者dont (dont)時間1年前 (2024/08/01 19:51)推噓2(2推 0噓 2→)

留言4則, 4人參與討論串613/1550 (看更多)

2678. Number of Senior Citizens ```python class Solution: def countSeniors(self, details: List[str]) -> int: # phone_number = s[:10] # gender = s[10] # age = s[11:13] # seat = s[13:] return sum(int(s[11:13]) > 60 for s in details) ``` -- 週賽408的ranking更新了第四題官方補上corner case的測資就WA了我還以為這場就直接不計分了哭啊 X = Y = 20 https://i.imgur.com/uPD7ulT.jpg

修正版的Code: 一樣是union find (N個圓+4個邊) 但在union的時候檢查連接點是否在方形內 ```python class UnionFind: def __init__(self, n): self.size = n+4 self.rank = [1] * (n+4) self.root = list(range(n+4)) 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 False 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 class Solution: def canReachCorner(self, X: int, Y: int, circles: List[List[int]]) -> bool: n = len(circles) uf = UnionFind(n) for i in range(n): xi, yi, ri = circles[i] for xj, yj in (X, Y), (0, 0): dist = (xi - xj) ** 2 + (yi - yj) ** 2 if ri ** 2 >= dist: return False if xi + ri >= X and 0 <= yi <= Y: # right uf.union(i, n) if xi - ri <= 0 and 0 <= yi <= Y: # left uf.union(i, n+1) if yi + ri >= Y and 0 <= xi <= X: # up uf.union(i, n+2) if yi - ri <= 0 and 0 <= xi <= X: # bottom uf.union(i, n+3) for j in range(i+1, n): xj, yj, rj = circles[j] if not (0 <= (xi + xj) / 2 <= X and 0 <= (yi + yj) / 2 <= Y): continue dist = (xi - xj) ** 2 + (yi - yj) ** 2 if (ri + rj) ** 2 >= dist: uf.union(i, j) r_right = uf.find(n) r_left = uf.find(n+1) r_top = uf.find(n+2) r_bottom = uf.find(n+3) if r_right == r_left or r_top == r_bottom or r_right == r_top or r_left == r_bottom: return False return True ``` -- http://i.imgur.com/OLvBn3b.jpg