0292. Nim Game¶
题目信息¶
- 题号:
0292
- 难度:
Easy
- 主题:
轮流取石子、最优策略、胜负判断
- 原题:
- 重点:
你先手、每回合必须拿 1 至 3 块、拿走最后一块者获胜、双方都按最优策略行动
题目重述¶
桌上最初有 n 块石头。你和对手轮流行动,由你先手;每次行动必须从剩余石头中拿走 1、2 或 3 块,拿走最后一块石头的人获胜。判断在双方都采用最优策略时,你是否能够保证获胜。
n 位于 [1, 2^31 - 1],因此游戏开始时至少有一块石头。函数只返回布尔结果:存在一种策略能让你无论对手如何最优应对都获胜时返回 true,否则返回 false;不需要输出具体的取石过程。
自建示例¶
先手处于必败局面:
输入:n = 8
输出:false
解释:无论先手拿 1、2 还是 3 块,对手都能把本轮两人的总取石数补成 4,最终由对手拿走最后一块。
先手可以建立优势:
输入:n = 10
输出:true
解释:先手先拿 2 块,留下 8 块;之后无论对手拿多少,先手都可使两次行动合计拿走 4 块,从而保证最后取完。
四块为一个必败周期¶
若轮到某人时剩余石子数是 4 的倍数,他拿走 1、2 或 3 块后都会留下一个非 4 的倍数给对手;
对手可以拿走 4-r 块(其中 r 是刚才拿走的数量),重新把局面变成 4 的倍数。
因此所有 4k 都是先手必败局面。
若剩余数不是 4 的倍数,先手可以拿走 n%4 块,把对手送入一个 4 的倍数局面。
从 n=1,2,3 的直接取完,到上述“每轮凑 4”的策略,得到完整的胜负分类。
正确性说明¶
4k 局面无论先手取多少都能被对手补回下一个较小的 4 倍数,最终由对手拿完;
非 4 倍数局面先手能一步转成 4 倍数,之后利用对手的取数保持周期,最后由先手取完。
所以先手必胜当且仅当 n % 4 != 0。
C++ 实现¶
class Solution {
public:
bool canWinNim(int n) {
return n % 4 != 0;
}
};
代码分析¶
只做一次取模,时间复杂度和额外空间均为 O(1);无需模拟对手或枚举取法,
因为策略证明已经把所有局面归类。输入保证为正数,n=0 的非题目语义不会影响实现。