LeetCode 题解工作台
施咒的最大总伤害
一个魔法师有许多不同的咒语。 给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。 已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ， power[i] - 1 ， power[i] + 1 或者 po…
7
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们可以先对数组 进行排序，用一个哈希表 来记录每个伤害值的出现次数，然后遍历数组 ，对于每个伤害值 ，我们可以得出使用伤害值为 的咒语时，可以使用的下一个伤害值的索引，即第一个大于 $x + 2$ 的伤害值的索引，我们可以使用二分查找来找到这个索引，记录在数组 中。 接下来，我们定义一个函数 ，用来计算从第 个伤害值开始，可以获得的最大伤害值。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
一个魔法师有许多不同的咒语。
给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。
已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。
每个咒语最多只能被使用 一次 。
请你返回这个魔法师可以达到的伤害值之和的 最大值 。
示例 1：
输入：power = [1,1,3,4]
输出：6
解释：
可以使用咒语 0，1，3，伤害值分别为 1，1，4，总伤害值为 6 。
示例 2：
输入：power = [7,1,6,6]
输出：13
解释：
可以使用咒语 1，2，3，伤害值分别为 1，6，6，总伤害值为 13 。
提示：
1 <= power.length <= 1051 <= power[i] <= 109
解题思路
方法一：二分查找 + 记忆化搜索
我们可以先对数组 进行排序，用一个哈希表 来记录每个伤害值的出现次数，然后遍历数组 ，对于每个伤害值 ，我们可以得出使用伤害值为 的咒语时，可以使用的下一个伤害值的索引，即第一个大于 的伤害值的索引，我们可以使用二分查找来找到这个索引，记录在数组 中。
接下来，我们定义一个函数 ，用来计算从第 个伤害值开始，可以获得的最大伤害值。
在 函数中，我们可以选择跳过当前伤害值，那么我们可以跳过当前伤害值的所有相同伤害值，直接跳到 ，可以获得的伤害值为 ；或者我们可以选择使用当前伤害值，那么我们可以使用当前伤害值的所有相同伤害值，然后跳到下一个伤害值的索引，可以获得的伤害值为 ，其中 表示第一个大于 的伤害值的索引。我们取这两种情况的最大值作为函数的返回值。
为了避免重复计算，我们可以使用记忆化搜索，将已经计算过的结果保存在数组 中，这样在计算 时，如果 不为 ，则直接返回 。
答案即为 。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def maximumTotalDamage(self, power: List[int]) -> int:
@cache
def dfs(i: int) -> int:
if i >= n:
return 0
a = dfs(i + cnt[power[i]])
b = power[i] * cnt[power[i]] + dfs(nxt[i])
return max(a, b)
n = len(power)
cnt = Counter(power)
power.sort()
nxt = [bisect_right(power, x + 2, lo=i + 1) for i, x in enumerate(power)]
return dfs(0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n + m log m), where n is the length of power and m is the number of unique powers, due to counting and sorting. Space complexity is O(m) for the hash table and dynamic programming array. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may emphasize using all spells of the same power when choosing to cast it.
- question_mark
Expect hints toward array scanning combined with hash lookup for efficiency.
- question_mark
Watch for discussions about handling large power values within the adjacency constraints.
常见陷阱
外企场景- error
Failing to sum all duplicates of a power before dynamic programming.
- error
Not properly skipping conflicting powers within the +-2 range.
- error
Assuming sequential indices matter instead of actual power values.
进阶变体
外企场景- arrow_right_alt
Allowing conflicts within a range k instead of 2.
- arrow_right_alt
Casting each spell at most once instead of summing duplicates.
- arrow_right_alt
Maximizing damage under additional cooldown constraints between casts.