EPISODE:179

LeetCode 筆記 - 1921. Eliminate Maximum Number of Monsters

發佈: 2023.11.07
閱讀: 約 1 分鐘
字數: 258

在這篇 LeetCode 第 1921 題的筆記中，我們探討了如何在怪物抵達堡壘前盡可能地將其消滅。解題關鍵在於預先計算每個怪物的到達時間並進行排序，以此制定最佳的攻擊順序。本文透過淺顯易懂的邏輯，帶領讀者掌握貪婪演算法在實戰中的應用。

題目在此 1921. Eliminate Maximum Number of Monsters

給訂兩個數列 dist 跟 speed，分別代表怪物的距離跟速度，每個回合可以前進 speed 個單位，在此同時我們可以選擇一個怪物攻擊，如果怪物的距離小於等於 0，堡壘則會被消滅。

請問最多可以消滅幾個怪物？

解題思維

這題的解法其實很簡單，就是先計算每個怪物到達堡壘的回合，接著排序，最後依序檢查回合數是否大於怪物抵達城市的回合數。

如此一來，就知道每個怪物是否可以在抵達城市前消滅掉。

程式碼

class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:

        if (size := len(dist)) == 1:
            return 1
        
        reach_rounds = [0] * size

        for i in range(size):
            reach_rounds[i] = dist[i] / speed[i]

        reach_rounds.sort()

        for i, r in enumerate(reach_rounds):
            if i >= r:
                return i

        return size

也許你也會想看看