Re: [閒聊] 每日leetcode

[dont (dont)]

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: 你好 新版友 請發錢
推 steven183: 錢
推 DJYOMIYAHINA: 大師 錢
→ dont: 不是應該反過來給我錢嗎QQ
推 zizc06719: 看來你不懂邊板     錢
推 sustainer123: 大師
→ NCKUEECS: 前
以上發完了 我沒錢ㄌ

推 mushrimp5466: 大師
噓 Lilchicken: 外來種 錢
※ 編輯: dont (218.35.11.142 臺灣), 07/13/2024 12:31:46