LeetCode 题解工作台
得到更多分数的最少关卡数目
给你一个长度为 n 的二进制数组 possible 。 Alice 和 Bob 正在玩一个有 n 个关卡的游戏，游戏中有一些关卡是 困难 模式，其他的关卡是 简单 模式。如果 possible[i] == 0 ，那么第 i 个关卡是 困难 模式，两个玩家 都不可能 通过。一个玩家通过一个简单模式的关…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 前缀和
答案摘要
我们先计算得到两个玩家能得到的分数和，记为 。 然后我们从小到大枚举玩家 能完成的关卡数目 ，计算玩家 得到的分数和 ，如果 $t > s - t$，那么玩家 需要完成的关卡数目就是 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 前缀和 题型思路
题目描述
给你一个长度为 n 的二进制数组 possible 。
Alice 和 Bob 正在玩一个有 n 个关卡的游戏，游戏中有一些关卡是 困难 模式，其他的关卡是 简单 模式。如果 possible[i] == 0 ，那么第 i 个关卡是 困难 模式，两个玩家 都不可能 通过。一个玩家通过一个简单模式的关卡可以获得 1 分，遇到困难模式的关卡将失去 1 分。
游戏的一开始，Alice 将从第 0 级开始 按顺序 完成一些关卡，然后 Bob 会完成剩下的所有关卡。
假设两名玩家都采取最优策略，目的是 最大化 自己的得分，Alice 想知道自己 最少 需要完成多少个关卡，才能获得比 Bob 更多的分数。
请你返回 Alice 获得比 Bob 更多的分数所需要完成的 最少 关卡数目，如果 无法 达成，那么返回 -1 。
注意，每个玩家都至少需要完成 1 个关卡。
示例 1：
输入：possible = [1,0,1,0]
输出：1
解释：
我们来看一下 Alice 可以完成的关卡数目：
- 如果 Alice 只完成关卡 0 ，Bob 完成剩下的所有关卡，那么 Alice 获得 1 分，Bob 获得 -1 + 1 - 1 = -1 分。
- 如果 Alice 完成到关卡 1 ，Bob 完成剩下的所有关卡，那么 Alice 获得 1 - 1 = 0 分，Bob 获得 1 - 1 = 0 分。
- 如果 Alice 完成到关卡 2 ，Bob 完成剩下的所有关卡，那么 Alice 获得 1 - 1 + 1 = 1 分，Bob 获得 -1 分。
Alice 需要完成至少一个关卡获得更多的分数。
示例 2：
输入：possible = [1,1,1,1,1]
输出：3
解释：
我们来看一下 Alice 可以完成的关卡数目：
- 如果 Alice 只完成关卡 0 ，Bob 完成剩下的所有关卡，那么 Alice 获得 1 分，Bob 获得 4 分。
- 如果 Alice 完成到关卡 1 ，Bob 完成剩下的所有关卡，那么 Alice 获得 2 分，Bob 获得 3 分。
- 如果 Alice 完成到关卡 2 ，Bob 完成剩下的所有关卡，那么 Alice 获得 3 分，Bob 获得 2 分。
- 如果 Alice 完成到关卡 3 ，Bob 完成剩下的所有关卡，那么 Alice 获得 4 分，Bob 获得 1 分。
Alice 需要完成至少三个关卡获得更多的分数。
示例 3：
输入：possible = [0,0]
输出：-1
解释：
两名玩家只能各完成 1 个关卡，Alice 完成关卡 0 得到 -1 分，Bob 完成关卡 1 得到 -1 分。两名玩家得分相同，所以 Alice 无法得到更多分数。
提示：
2 <= n == possible.length <= 105possible[i]要么是0要么是1。
解题思路
方法一：枚举
我们先计算得到两个玩家能得到的分数和，记为 。
然后我们从小到大枚举玩家 能完成的关卡数目 ，计算玩家 得到的分数和 ，如果 ，那么玩家 需要完成的关卡数目就是 。
如果枚举完前 个关卡都没有找到满足条件的 ，那么就返回 。
时间复杂度 ，其中 是数组的长度。空间复杂度 。
class Solution:
def minimumLevels(self, possible: List[int]) -> int:
s = sum(-1 if x == 0 else 1 for x in possible)
t = 0
for i, x in enumerate(possible[:-1], 1):
t += -1 if x == 0 else 1
if t > s - t:
return i
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each element is processed once during the transformation and prefix sum calculation. Space complexity is O(n) for storing prefix sums, though it can be optimized to O(1) using a running total instead of an array. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for efficient conversion of 0s to -1s to simplify net gain calculation.
- question_mark
Expect prefix sum usage to determine Alice's advantage quickly without nested loops.
- question_mark
Watch out for edge cases where all levels are impossible or Alice cannot surpass Bob.
常见陷阱
外企场景- error
Forgetting to convert 0s to -1s, which leads to incorrect net point computation.
- error
Not considering the case where Alice cannot gain more points and returning an invalid index.
- error
Calculating Bob's points incorrectly by not accounting for sequential play split.
进阶变体
外企场景- arrow_right_alt
Find minimum levels Alice must play when some levels have variable points instead of 1 or -1.
- arrow_right_alt
Determine maximum points Alice can achieve using the same prefix sum approach.
- arrow_right_alt
Apply the array plus prefix sum pattern to multiple players instead of just Alice and Bob.