0292. Nim 游戏

• 标签：脑筋急转弯、数学、博弈
• 难度：简单

题目链接

• 0292. Nim 游戏 - 力扣

题目大意

两个人玩 Nim 游戏。游戏规则是这样的：

• 桌上有一堆石子，两个人轮流从石子堆中拿走 1~3 块石头。拿掉最后一块石头的人就是获胜者。

• 假如每个人都尽可能的想赢得比赛，所以每一轮都是最优解。

现在给定一个整数 n 代表石头数目。如果你作为先手，问最终能否赢得比赛。

解题思路

假设石子的数量为 1~3，那么我作为先手，肯定第一次就将所有的石子都拿完了，所以肯定能赢。

假设石子的数量为 4，那么我作为先手，无论第一次拿走 1、2、3 块石头，都不能拿完，而第二个人再拿的时候，会直接将剩下的石头一次性全拿走，所以肯定不会赢。

如果石子数量多于 4，那么我作为先手，为了赢，应该尽可能使得本轮拿走后的石子数为 4，这样对手拿完一次之后，自己肯定会获胜。

所以石子树为 5、6、7 块的时候，我可以通过分别拿走 1、2、3 块石头，使得剩下的石头数为 4，从而在下一轮获得胜利。

如果石子数为 8 块的时候，我无论怎么拿都不能使剩下石子为 4。而对方又会利用这个机会使得他拿走之后的石子数变为 4，从而使我失败。

所以，很显然：当 n 不是 4 的整数倍时，我一定赢得比赛。当 n 为 4 的整数倍时，我一定赢不了比赛。

代码

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0