LeetCode 292. Nim 游戏
题目描述
题意分析
桌面上有
n块石头，两人轮流取走石头，你先手。每次必须取一到三块，取到最后一块的人获胜；判断双方都采用最优策略时，你是否一定能赢。这里判断的是是否存在必胜策略，不能依赖对手犯错，也不是要求每次都取最多的三块。题目保证
n为正数，只需要返回胜负，不需要模拟整场游戏。
解法：数学结论
核心思路
[!blue]
把轮到某人行动时的剩余石头数看作一个局面。能通过一次合法选择把对手送到必败局面的，是必胜局面；无论怎么选都会给对手留下必胜局面的，就是必败局面。
剩下一到三块时，当前玩家可以直接拿完获胜。面对四的倍数时，先行动的一方无论拿走
t块，另一方都可以再拿4 - t块；两次合计恰好拿走四块，而且补取数量仍在一到三的合法范围内。这样，每轮结束后都把更小的四倍数留给原先行动的一方。最后剩四块时，原先行动者仍拿不完，采用补足策略的一方会拿走最后一块。因此面对四倍数的玩家无法在对手最优时获胜。
若
n不是四的倍数，余数r = n % 4必为一到三。先手先拿走这r块：若已经拿完就直接获胜，否则给对手留下四的倍数。随后对手每次取t块，自己就取4 - t块，保持同一策略直到拿到最后一块。所以胜负只由是否为四的倍数决定，返回
n % 4 != 0。周期中的四来自“一次对手行动与一次回应合计四块”，不是最大单次取量三。
解题步骤
- 计算
n对四的余数。- 余数非零，先手可以取走余数并保持补足策略，返回真。
- 余数为零，对手可以保持补足策略，返回假。
代码实现
class Solution {
// 如果先手面对 4 的倍数，无论拿 1、2、3 块，对手都能补到 4，让先手再次面对 4 的倍数。
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}
func canWinNim(n int) bool {
// 如果先手面对 4 的倍数，无论拿 1、2、3 块，对手都能补到 4，让先手再次面对 4 的倍数。
return n%4 != 0
}
复杂度分析
- 时间复杂度：$O(1)$，只做一次取余与比较，不随石头数模拟回合。
- 空间复杂度：$O(1)$，不保存博弈状态表。
关键点总结
[!green]
- 最优博弈要判断能否把必败局面交给对手，不能只考察某种固定取法。
- 四倍数是必败态，其他正数都能一步到达它或直接结束游戏。
- 结论依赖每次取一到三块以及拿最后一块获胜这两条规则。
易错点总结
[!yellow]
- 把四倍数当成必胜态，会把“留给对手的局面”与“自己面对的局面”混淆。
- 只按奇偶判断，无法描述每次有三种合法选择时的胜负周期。
- 以最大可取量三为模数，忽略了双方两次行动可以合计为四的回应策略。
- 认为必须始终取三块，会错过根据余数和对手行动调整取法的必胜策略。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1510. 石子游戏 IV | 困难 | 同样是轮流取石子的必胜态分析，原题允许取平方数，不能直接套本题按4取模的规律。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！