292. Nim游戏

题目描述：

你和你的朋友，两个人一起玩 Nim 游戏：

• 桌子上有一堆石头。
• 你们轮流进行自己的回合， 你作为先手 。
• 每一回合，轮到的人拿掉 1 - 3 块石头。
• 拿掉最后一块石头的人就是获胜者。 假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

示例 1：

输入：n = 4
输出：false 
解释：以下是可能的结果:
1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
3. 你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
在所有结果中，你的朋友是赢家。

示例 2：

输入：n = 1
输出：true

示例 3：

输入：n = 2
输出：true

提示：

• 1 <= n <= 2^31 - 1

---

解题分析及思路：

Nim 游戏是一种数学博弈，基于异或运算的一种变形。要解决这个问题，首先要理解 Nim 游戏的背后数学原理，然后使用这些原理来判断在给定石头数量的情况下是否能够获胜。

Nim 游戏的背后原理：

1. 基本原理： Nim 游戏的基本原理是通过控制剩余的石头数量，使得轮到对手的时候，无论他拿多少块石头，你都能以相应的方式回应，确保最后轮到你时，最后一块石头能够被你拿走。

2. 异或运算： Nim 游戏中，如果一堆石头的数量被表示为 a1 ^ a2 ^ … ^ an，其中 ^ 表示异或运算，如果结果等于0，那么先手必输，否则先手必胜。

在理解了 Nim 游戏的基本原理后，我们可以得到一个简单的结论：

• 如果石头数量 n 对 4 取模等于 0，那么先手必输；
• 否则，先手必胜。

这是因为如果石头数量对 4 取模等于 0，无论先手拿多少块石头，对手都可以通过一定的策略确保每一轮结束后石头数量仍然对 4 取模等于 0。而如果石头数量对 4 取模不等于 0，先手总能通过一定的策略确保每一轮结束后石头数量对 4 取模等于 0。

func canWinNim(n int) bool {
	return n%4 != 0
}

这个简单的函数通过判断石头数量对 4 取模是否等于 0来确定是否能够赢得 Nim 游戏。如果等于 0，则返回 False，否则返回 True。

这是因为如果石头数量对 4 取模等于 0，先手必输；否则，先手必胜。所以 n % 4 != 0 判断是否能够赢得游戏。

复杂度：

• 时间复杂度：O(1)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:1.8 MB,击败了74.14% 的Go用户