难度: Easy
你和你的朋友，两个人一起玩 Nim 游戏：
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 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 <= 231 - 1运行时间: 16 ms
内存: 0.0 MB
class Solution:
def canWinNim(self, n: int) -> bool:
return n % 4 != 0
该题解使用了数学归纳法的思路。通过观察，可以发现如果石头数量 n 不是 4 的倍数，那么先手总是可以赢得比赛。因为无论后手如何选择，先手总可以选择 1、2 或 3 颗石头，使得剩余石头数量继续保持不是 4 的倍数，直到最后先手取走最后一颗石头获胜。而当石头数量 n 是 4 的倍数时，无论先手如何选择，剩余的石头数量一定会成为 4 的倍数，此时后手就可以使用相同的策略来获胜。因此，只需要判断 n 是否是 4 的倍数即可确定先手是否能够获胜。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def canWinNim(self, n: int) -> bool:
# 如果石头数量 n 不是 4 的倍数，那么先手总是可以赢得比赛
return n % 4 != 0
在Nim游戏中，如果石头总数是4的倍数，无论先手拿走多少颗石头（1、2或3颗），剩下的石头数量仍然是4的倍数的减一，这导致后手总可以通过拿走剩余石头与4的差值（1、2或3颗）来使剩余的石头数量再次成为4的倍数。这样的拿取策略让后手总能掌控游戏局势，使得最终先手面对恰好为4的石头数量时无法赢得比赛，因为无论先手拿走多少颗，后手总能在下一轮拿走所有剩余石头。
是的，这种判断对于其他数量的石头同样有效。因为如果石头数量不是4的倍数，先手总可以通过拿走1至3颗石头中的适当数量，使剩下的石头数量变成4的倍数。之后，无论后手如何拿，先手都可以继续使剩下的石头数量保持不是4的倍数，直至最后一次拿走所有剩余石头获胜。
这个策略的实施基于先手控制游戏的能力。假设初始石头数量不是4的倍数，先手可以选择拿走1至3颗中的某个数量，使总数变为最近的低于当前数量的4的倍数。例如，如果有5颗石头，先手拿走1颗，剩下4颗；如果有6颗石头，先手拿走2颗，剩下4颗；如果有7颗石头，先手拿走3颗，剩下4颗。这样，后手每次只能应对已经是4的倍数的情况，而先手总能保持这种优势直到游戏结束。
如果游戏规则变为允许每次拿走1至4块石头，原有的策略需要调整。因为在这种新规则下，当剩余石头数量为4时，先手可以一次性拿走所有石头而直接获胜。因此，策略将转变为确保每次操作后剩余的石头数量不是5的倍数，因为这会给对手一个将剩余石头减至4的机会。所以，新的关键数字从4变为5。