Re: [閒聊] 每日leetcode已回收

看板Marginalman作者dont (dont)時間1年前 (2024/07/13 12:15)推噓5(6推 1噓 2→)

留言9則, 9人參與討論串487/1554 (看更多)

2751. Robot Collisions ## 思路 Sort by position maintain一個往右走的stack (to_right) 如果遇到往左走的就比較大小, 照三種情形更新healths 最後回傳所有 >0 的health ## Complexity Time Complexity: O(N logN) # sort, 用counting sort O(N) Space Complexity: O(N) # stack ## Code ```python class Solution: def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]: n = len(positions) heap = [] for idx, (pos, d) in enumerate(zip(positions, directions)): heapq.heappush(heap, (pos, d, idx)) to_right = [] while heap: pos, d, idx = heapq.heappop(heap) if d == 'R': to_right.append(idx) continue while to_right and healths[idx]: if healths[to_right[-1]] > healths[idx]: healths[to_right[-1]] -= 1 healths[idx] = 0 break elif healths[to_right[-1]] == healths[idx]: healths[idx] = healths[to_right.pop()] = 0 else: healths[idx] -= 1 healths[to_right.pop()] = 0 return [health for health in healths if health] ``` 太習慣直接用heap.. 改用indices.sort直接快200ms: indices = list(range(n)) indices.sort(key=lambda x: positions[x]) for idx in indices: -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.135 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720844112.A.4C7.html

推

oin1104

07/13 12:16, 1年前 , 1^F

07/13 12:16, 1^F

推

steven183

07/13 12:16, 1年前 , 2^F

07/13 12:16, 2^F

推

DJYOMIYAHINA

07/13 12:16, 1年前 , 3^F

07/13 12:16, 3^F