leetcode
leetcode 2101 ~ 2150
杀死所有怪物的最短时间

杀死所有怪物的最短时间

难度:

标签:

题目描述

代码结果

运行时间: 1997 ms, 内存: 24.6 MB


/*
题目思路:
1. 我们需要找到杀死所有怪物的最短时间。
2. 假设每个怪物的初始生命值在一个数组中,每次攻击可以减少固定的生命值。
3. 我们可以用二分查找法找到最小的时间,在这个时间内可以杀死所有怪物。
4. 使用Java Streams来简化代码。
*/
import java.util.Arrays;

public class KillMonstersStream {
    public static int minTimeToKillMonsters(int[] health, int damagePerSecond) {
        int left = 0;
        int right = Integer.MAX_VALUE;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canKillAllMonsters(health, damagePerSecond, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private static boolean canKillAllMonsters(int[] health, int damagePerSecond, int time) {
        return Arrays.stream(health).allMatch(h -> h <= time * damagePerSecond);
    }

    public static void main(String[] args) {
        int[] health = {10, 20, 30};
        int damagePerSecond = 10;
        System.out.println(minTimeToKillMonsters(health, damagePerSecond)); // Output: 3
    }
}

解释

方法:

这个题解使用了动态规划的策略来求解杀死所有怪物的最短时间。首先,power数组中的每个元素代表每个怪物的力量。算法的核心是使用一个字典dp,其键是一个整数,表示已选择杀死怪物的组合的位掩码,值是完成这个组合所需的最小时间。对于每个可能的组合,它计算了使用不同顺序杀死怪物的成本,并保留了成本最小的时间。这里,每个怪物的杀死时间是怪物的力量除以(已经杀死的怪物数量+1),这反映了随着时间的推移而逐渐增加的能力。动态规划数组在每一步都更新,保存了截至目前为止的所有可能的组合和它们对应的最短完成时间。

时间复杂度:

O(n * 2^n)

空间复杂度:

O(2^n)

代码细节讲解

🦆
为什么在动态规划中使用位掩码来表示怪物的组合,而不是其他数据结构如列表或集合?
位掩码是一种高效的方式来表示组合问题中的状态。在处理如杀死怪物的组合问题时,位掩码通过整数的每个二进制位来表示某个元素是否被选中(例如,怪物是否已被杀死)。这使得状态的转移(即从一个怪物组合到另一个怪物组合的过渡)非常高效,因为它可以通过位运算如AND、OR和XOR来实现。此外,相比于列表或集合,位掩码在空间效率和访问速度上通常有优势,这对于动态规划解法中频繁的状态更新和查询尤为重要。
🦆
题解中没有明确说明如何处理边界情况,例如`power`数组为空时的情况,这种情况下算法的行为和输出是什么?
在`power`数组为空时,代表没有怪物需要被杀死。题解中已经通过初始化`dp = {0: 0}`来处理这种情况,这里`dp[0]`表示没有选择任何怪物时的最短时间为0。因此,如果`power`数组为空,那么在执行动态规划的过程中不会有任何怪物的组合被添加到`dp`中,最终函数会返回`dp[0]`的值,即0。这意味着在没有怪物的情况下,最短时间自然是0分钟。

相关问题