LeetCode 题解工作台
石子游戏 IX
Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ，其中 stones[i] 是第 i 个石子的价值。 Alice 和 Bob 轮流进行自己的回合， Alice 先手。每一回合，玩家需要从 stones …
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
由于玩家的目标是使得已移除石子的价值总和不能被 整除，因此我们只需要考虑每个石子的价值对 的余数即可。 我们用一个长度为 的数组 维护当前剩余石子的价值对 的余数的个数，其中 表示余数为 的个数，而 和 分别表示余数为 和 的个数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ，其中 stones[i] 是第 i 个石子的价值。
Alice 和 Bob 轮流进行自己的回合，Alice 先手。每一回合，玩家需要从 stones 中移除任一石子。
- 如果玩家移除石子后，导致 所有已移除石子 的价值 总和 可以被 3 整除，那么该玩家就 输掉游戏 。
- 如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。
假设两位玩家均采用 最佳 决策。如果 Alice 获胜，返回 true ；如果 Bob 获胜，返回 false 。
示例 1：
输入：stones = [2,1] 输出：true 解释：游戏进行如下： - 回合 1：Alice 可以移除任意一个石子。 - 回合 2：Bob 移除剩下的石子。 已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此，Bob 输，Alice 获胜。
示例 2：
输入：stones = [2] 输出：false 解释：Alice 会移除唯一一个石子，已移除石子的值总和为 2 。 由于所有石子都已移除，且值总和无法被 3 整除，Bob 获胜。
示例 3：
输入：stones = [5,1,2,4,3] 输出：false 解释：Bob 总会获胜。其中一种可能的游戏进行方式如下： - 回合 1：Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。 - 回合 2：Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 = 1 + 3 = 4 。 - 回合 3：Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 = 1 + 3 + 4 = 8 。 - 回合 4：Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 = 10. - 回合 5：Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 + 5 = 15. Alice 输掉游戏，因为已移除石子值总和（15）可以被 3 整除，Bob 获胜。
提示：
1 <= stones.length <= 1051 <= stones[i] <= 104
解题思路
方法一：贪心 + 分情况讨论
由于玩家的目标是使得已移除石子的价值总和不能被 整除，因此我们只需要考虑每个石子的价值对 的余数即可。
我们用一个长度为 的数组 维护当前剩余石子的价值对 的余数的个数，其中 表示余数为 的个数，而 和 分别表示余数为 和 的个数。
在第一回合，Alice 不能移除余数为 的石子，因为这样会使得已移除石子的价值总和能被 整除。因此，Alice 只能移除余数为 或 的石子。
我们首先考虑 Alice 移除余数为 的石子的情况。如果 Alice 移除了一个余数为 的石子，石子 对石子价值总和对 的余数不会改变，因此价值对 的余数为 的石子可以在任意回合被移除，我们暂时不考虑。所以 Bob 也只能移除余数为 的石子，之后 Alice 移除余数为 的石子，依次进行，序列为 。在这种情况下，如果最终回合数为奇数，且还有剩余石子，那么 Alice 获胜，否则 Bob 获胜。
对于第一回合 Alice 移除余数为 的石子的情况，我们可以得到类似的结论。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
class Solution:
def stoneGameIX(self, stones: List[int]) -> bool:
def check(cnt: List[int]) -> bool:
if cnt[1] == 0:
return False
cnt[1] -= 1
r = 1 + min(cnt[1], cnt[2]) * 2 + cnt[0]
if cnt[1] > cnt[2]:
cnt[1] -= 1
r += 1
return r % 2 == 1 and cnt[1] != cnt[2]
c1 = [0] * 3
for x in stones:
c1[x % 3] += 1
c2 = [c1[0], c1[2], c1[1]]
return check(c1) or check(c2)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's understanding of greedy strategies and game theory principles.
- question_mark
Evaluate the candidate's ability to reduce the problem to manageable steps using mathematical properties like modulo.
- question_mark
Assess how well the candidate tracks state transitions and invariants during the game.
常见陷阱
外企场景- error
Forgetting to properly track the sum modulo 3, leading to incorrect results when determining if the sum is divisible by 3.
- error
Assuming that the game can be solved without considering the sequence of moves by both players, which might lead to overlooking certain optimal strategies.
- error
Not recognizing that the game's outcome depends on both players making the best possible moves, requiring a deeper understanding of optimal play.
进阶变体
外企场景- arrow_right_alt
Consider a version where players can remove multiple stones per turn. This would introduce more complex strategic elements to the game.
- arrow_right_alt
What if the sum of the removed stones has to be divisible by 5 instead of 3? This variant would alter the modulo strategy and game flow.
- arrow_right_alt
Introduce a rule where the player who makes the first move after a certain number of turns must remove two stones instead of one. This change would impact the optimal strategy.