LeetCode 292简单数学
Nim 游戏 图解题解
这道题到底在问什么
你和朋友轮流玩 Nim 游戏：桌上有一堆石头，你作为先手。每一回合，轮到的人拿掉 1 到 3 块石头，拿掉最后一块石头的人获胜。假设双方每一步都是最优解，请判断给定石头数量 n 时你是否可以赢。
- 输入
- n = 4
- 输出
- false
- 解释
- 无论先手拿 1、2、3 块，对手都能拿走剩下的最后一块。
- 输入
- n = 1
- 输出
- true
- 输入
- n = 2
- 输出
- true
最优解：一步一步想明白
- 3博弈题常常先看小局面：哪些 n 先手必胜，哪些 n 先手必败。
- 4真正的不变量是：如果你能让对手面对 4k，那么无论对手拿 1、2、3，你都能补成一轮拿走 4。
- 5n % 4 = 1只剩 1 块时，先手直接拿完，返回 true。
- 6n % 4 = 2只剩 2 块时，先手也能一次拿完。
- 7n % 4 = 3只剩 3 块时，先手仍然能一次拿完。
- 8n % 4 = 04 是第一个必败态：先手不能拿 4，只能把 1、2、3 这类必胜态交给对手。
- 9n % 4 = 15 不是 4 的倍数，先手可以拿 1，让对手面对必败态 4。
- 10n % 4 = 2同理，6 可以拿 2；对手接手 4，就会陷入必败。
- 11n % 4 = 37 可以拿 3。你要做的不是拿最多，而是把对手送到 4 的倍数。
- 12n % 4 = 08 和 4 一样：先手拿完后一定把非 4 倍数交给对手，对手再把你送回 4 的倍数。
- 13return n % 4 != 0所以代码只需要判断 n 是否为 4 的倍数：是就先手必败，否则先手拿掉 n%4 块，把 4 的倍数留给对手。
- 16这就是为什么 4 的倍数是先手必败态，其他数量都是先手必胜态。
⚠️ 容易写错的地方
✗ 错：递归搜索所有走法
✓ 对：直接判断 n % 4
n 很大，游戏树会爆炸；必败态有固定周期。
✗ 错：n=4 返回 true
✓ 对：n=4 返回 false
先手最多拿 3 块，无法直接拿完。
✗ 错：以为拿最多总最好
✓ 对：目标是把 4 的倍数留给对手
博弈题看的是对手接下来面对什么局面。
完整代码（Python）
Python
class Solution:
def canWinNim(self, n):
return n % 4 != 0复杂度
时间复杂度
O(1)
只做一次取模判断。
空间复杂度
O(1)
不需要递归、DP 表或额外数组。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 Nim 游戏 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「数学」，换最直接的暴力解会差在哪？+
数学抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。