292. Nim 游戏
题目描述
你和朋友玩一个取石子游戏。桌上有一堆共 n 块石子，两人轮流行动，你先手。
轮到谁，谁就从堆里拿走 1 块、2 块或 3 块石子。拿到最后一块石子的人获胜。
假设双方每一步都采取最优策略。输入 n，你一定能赢时返回 true，否则返回 false。
示例 1
输入：n = 4 输出：false
解释：不论你先拿 1、2 还是 3 块，朋友都能把剩下的石子一次拿光，所以你必输。
示例 2
输入：n = 1 输出：true
解释：你直接拿走唯一的一块。
示例 3
输入：n = 2 输出：true
解释：你一次拿走两块。
数据范围
1 <= n <= 2^31 - 1
解题思路
从小往大分析必败态：n = 1, 2, 3 可以一次拿完，必胜；n = 4 无论怎么拿都给对手留下 1~3 块，必败。一般地，如果 n 不是 4 的倍数，就拿 n % 4 块，把 4 的倍数留给对手；之后对手拿 k 块，你就拿 4 - k 块，始终保持 4 的倍数，最后一块必然是你拿。反之 n 是 4 的倍数，对手可以用同样策略对付你。
为什么正确
先手必败 ⇔ n % 4 == 0。
复杂度分析
时间 O(1)，空间 O(1)。
易错点
n 最大为 2^31-1，用动态规划逐个推算会超时或超内存，要用 n % 4 的结论。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def canWinNim(self, n: int) -> bool:
return n % 4 != 0class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}class Solution {
public:
bool canWinNim(int n) {
return n % 4 != 0;
}
};func canWinNim(n int) bool {
return n%4 != 0
}var canWinNim = function(n) {
return n % 4 !== 0;
};function canWinNim(n: number): boolean {
return n % 4 !== 0;
}