难度：⭐
题目描述：
你和你的朋友，两个人一起玩 Nim 游戏：
- 桌子上有一堆石头。
- 你们轮流进行自己的回合，你作为先手。
- 每一回合，轮到的人拿掉 1 - 3 块石头。
- 拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
示例1：
1 | 输入：n = 4 |
示例2：
1 | 输入：n = 1 |
示例3：
1 | 输入：n = 2 |
提示：
1 <= n <= 231 - 1
解题过程：
思路：
题目看起来有点东西，其实分析起来很简单：
甲乙玩游戏，甲先手，石头数量为n，每一回合拿1-3块
- n为1、2、3时，先手（甲）胜
- n为4时，甲无论拿1块、2块、3块都是后手（乙）胜
- n为5、6、7时，甲总可以拿后剩下4块，这样到乙的回合，可以看成是情况2，甲为后手甲胜。
- n为8时，甲拿完后可以看成情况3，对乙来说，乙为先手乙胜。
- ……
总结可以得出n为4的倍数时后手（乙）胜，其他情况先手（甲）胜。
c++代码：(执行用时0ms，击败100.00%，内存消耗6.2M，击败12.24%）
1 | class Solution { |
官方题解:
如果堆中石头的数量 nn 不能被 44 整除，那么你总是可以赢得 Nim 游戏的胜利。
推理
让我们考虑一些小例子。显而易见的是，如果石头堆中只有一块、两块、或是三块石头，那么在你的回合，你就可以把全部石子拿走，从而在游戏中取胜。而如果就像题目描述那样，堆中恰好有四块石头，你就会失败。因为在这种情况下不管你取走多少石头，总会为你的对手留下几块，使得他可以在游戏中打败你。因此，要想获胜，在你的回合中，必须避免石头堆中的石子数为 4 的情况。
同样地，如果有五块、六块、或是七块石头，你可以控制自己拿取的石头数，总是恰好给你的对手留下四块石头，使他输掉这场比赛。但是如果石头堆里有八块石头，你就不可避免地会输掉，因为不管你从一堆石头中挑出一块、两块还是三块，你的对手都可以选择三块、两块或一块，以确保在再一次轮到你的时候，你会面对四块石头。
显然，它以相同的模式不断重复 $n=4,8,12,16,\dots$基本可以看出是 $4$ 的倍数。
Java代码：
1 | public boolean canWinNim(int n) { |
复杂度分析
- 时间复杂度：$O(1)$，只进行了一次检查。
- 空间复杂度：$O(1)$，没有使用额外的空间。
总结：
官方题解和我的思路一样，想明白了也挺简单的，看到官方题解下一些评论说自己是sb???也还好吧,简简单单
