LeetCode 题解工作台
令牌放置
你的初始 能量 为 power ，初始 分数 为 0 ，只有一包令牌以整数数组 tokens 给出。其中 tokens[i] 是第 i 个令牌的值（下标从 0 开始）。 你的目标是通过有策略地使用这些令牌以 最大化 总 分数 。在一次行动中，你可以用两种方式中的一种来使用一个 未被使用的 令牌（但不…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
令牌的使用方法有两种，一种是消耗能量得到分数，一种是消耗分数得到能量。显然，我们应该消耗尽可能少的能量来得到尽可能多的分数。 因此，我们可以将令牌按照消耗能量的多少进行排序，然后使用双指针，一个指针从左向右遍历，一个指针从右向左遍历，每次遍历都尽可能地消耗能量得到分数，然后更新最大分数。如果当前能量不足以消耗当前令牌，那么我们就尝试使用分数来消耗当前令牌，如果分数不足以消耗当前令牌，那么我们就停止…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
你的初始 能量 为 power，初始 分数 为 0，只有一包令牌以整数数组 tokens 给出。其中 tokens[i] 是第 i 个令牌的值（下标从 0 开始）。
你的目标是通过有策略地使用这些令牌以 最大化 总 分数。在一次行动中，你可以用两种方式中的一种来使用一个 未被使用的 令牌（但不是对同一个令牌使用两种方式）：
- 朝上：如果你当前 至少 有
tokens[i]点 能量 ，可以使用令牌i，失去tokens[i]点 能量 ，并得到1分 。 - 朝下：如果你当前至少有
1分 ，可以使用令牌i，获得tokens[i]点 能量 ，并失去1分 。
在使用 任意 数量的令牌后，返回我们可以得到的最大 分数 。
示例 1：
输入：tokens = [100], power = 50 输出：0 解释：因为你的初始分数为0，无法使令牌朝下。你也不能使令牌朝上因为你的能量（50）比tokens[0]少（100）。
示例 2：
输入：tokens = [200,100], power = 150
输出：1
解释：使令牌 1 正面朝上，能量变为 50，分数变为 1 。
不必使用令牌 0，因为你无法使用它来提高分数。可得到的最大分数是 1。
示例 3：
输入：tokens = [100,200,300,400], power = 200 输出：2 解释：按下面顺序使用令牌可以得到 2 分： 1. 令牌 0 (100)正面朝上，能量变为100，分数变为12. 令牌 3 (400)正面朝下，能量变为500，分数变为03. 令牌 1 (200)正面朝上，能量变为300，分数变为14. 令牌 2 (300)正面朝上，能量变为0，分数变为2可得的最大分数是 2。
提示：
0 <= tokens.length <= 10000 <= tokens[i], power < 104
解题思路
方法一：贪心 + 排序 + 双指针
令牌的使用方法有两种，一种是消耗能量得到分数，一种是消耗分数得到能量。显然，我们应该消耗尽可能少的能量来得到尽可能多的分数。
因此，我们可以将令牌按照消耗能量的多少进行排序，然后使用双指针，一个指针从左向右遍历，一个指针从右向左遍历，每次遍历都尽可能地消耗能量得到分数，然后更新最大分数。如果当前能量不足以消耗当前令牌，那么我们就尝试使用分数来消耗当前令牌，如果分数不足以消耗当前令牌，那么我们就停止遍历。
时间复杂度 ，空间复杂度 。其中 是令牌的数量。
class Solution:
def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
tokens.sort()
ans = score = 0
i, j = 0, len(tokens) - 1
while i <= j:
if power >= tokens[i]:
power -= tokens[i]
score, i = score + 1, i + 1
ans = max(ans, score)
elif score:
power += tokens[j]
score, j = score - 1, j - 1
else:
break
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \log n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Candidate uses a two-pointer approach with the correct greedy strategy.
- question_mark
Candidate efficiently handles edge cases, such as no tokens or very low power.
- question_mark
Candidate can explain how the sorting step simplifies the problem and ensures optimal performance.
常见陷阱
外企场景- error
Failing to correctly manage the two-pointer approach, leading to inefficient use of power.
- error
Not handling edge cases like an empty token array or insufficient power correctly.
- error
Incorrectly prioritizing tokens without considering the optimal sequence, which could result in a lower score.
进阶变体
外企场景- arrow_right_alt
Allowing the playing of tokens multiple times, either face-up or face-down, with adjusted rules.
- arrow_right_alt
Limiting the number of tokens that can be played face-up or face-down, adding another layer of strategy.
- arrow_right_alt
Adding power regeneration or token costs that affect the ability to play tokens, altering the dynamics of the problem.