0292. Nim Game ============== 题目信息 -------- :题号: 0292 :难度: Easy :主题: 轮流取石子、最优策略、胜负判断 :原题: `LeetCode 0292 `_ :重点: 你先手、每回合必须拿 1 至 3 块、拿走最后一块者获胜、双方都按最优策略行动 题目重述 -------- 桌上最初有 ``n`` 块石头。你和对手轮流行动,由你先手;每次行动必须从剩余石头中拿走 ``1``、``2`` 或 ``3`` 块,拿走最后一块石头的人获胜。判断在双方都采用最优策略时,你是否能够保证获胜。 ``n`` 位于 ``[1, 2^31 - 1]``,因此游戏开始时至少有一块石头。函数只返回布尔结果:存在一种策略能让你无论对手如何最优应对都获胜时返回 ``true``,否则返回 ``false``;不需要输出具体的取石过程。 自建示例 -------- 先手处于必败局面: .. code-block:: text 输入:n = 8 输出:false 解释:无论先手拿 1、2 还是 3 块,对手都能把本轮两人的总取石数补成 4,最终由对手拿走最后一块。 先手可以建立优势: .. code-block:: text 输入: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++ 实现 -------- .. code-block:: cpp class Solution { public: bool canWinNim(int n) { return n % 4 != 0; } }; 代码分析 -------- 只做一次取模,时间复杂度和额外空间均为 ``O(1)``;无需模拟对手或枚举取法, 因为策略证明已经把所有局面归类。输入保证为正数,``n=0`` 的非题目语义不会影响实现。