040 · Nim Game
My First Thoughts
这道题固定了我是先手，目标是给一个 n，判断我在双方都最优的情况下能不能赢。
例子其实已经给得比较明确了。先从小数字看：
n = 1, 2, 3我都可以直接一次拿完，所以我赢。
到了：
n = 4我就必败。因为我只能拿 1、2 或 3 个，剩下的石头一定会被对方一次拿完。
继续往后看：
n = 5, 6, 7我又可以赢。因为我可以先拿走一些石头，把 4 留给对方。
再到：
n = 8我又会输。
这个规律就比较明显了：关键数字是 4。
可以这样理解：
到最后只剩下
4个的时候，谁需要先取，谁就输。
换句话说，如果想让对方输，就尽量把 4 个石头留给对方。
更一般地看，如果 n 是 4 的倍数，我就是必败的。因为不管我取多少个，假设我取了 m 个，对方只要每次取：
4 - m这样两个人这一轮合起来正好取走 4 个。局面会一直回到 4 的倍数，最后就会轮到我面对 4 个石头。
同样的道理，只要 n 不是 4 的倍数，我就可以先取走那个余数，让剩下的石头数变成 4 的倍数。这样就把必败局面交给对方。
所以这题其实不是要模拟每一步，而是判断：
n 是不是 4 的倍数如果可以选择先手或后手，那就是必胜：n 是 4 的倍数时选后手，不是 4 的倍数时选先手。这样总能把必败局面交给对方。
但 LeetCode 这题固定我是先手，所以胜负才只取决于数字本身。每 4 个数里只有 4 的倍数是先手必败，其他三种余数都是先手必赢，所以固定先手时可以理解成先手赢面是 3/4。
Why That Is Not Enough
这个思路已经完整了。剩下要做的只是把口头规律压成一个布尔表达式。
题目问的是：
我是否一定能赢所以返回值应该是：
- 如果
n是4的倍数，返回False - 如果
n不是4的倍数，返回True
在 Python 里，“是不是 4 的倍数”可以用取余判断：
n % 4 == 0因此“我能赢”就是它的反面：
n % 4 != 0Final Idea
关键规律是：
只要我能把
4的倍数留给对方，对方就在必败局面里。
如果 n 不是 4 的倍数，比如：
n = 5, 6, 7我可以分别先拿走：
1, 2, 3这样剩下的就是 4，交给对方。
如果 n 是更大的非 4 倍数，比如：
n = 10我先拿走 2，剩下 8，还是 4 的倍数。
之后对方每次拿 m 个，我就拿 4 - m 个，让两个人一轮合起来拿走 4 个。这样局面一直保持在 4 的倍数上，最后对方会面对无法翻盘的局面。
反过来，如果一开始 n 就是 4 的倍数，我没有办法第一步还把 4 的倍数留给对方。无论我拿 1、2 还是 3 个，对方都能用同样的补数策略把局面重新变回 4 的倍数。
所以最终判断就是：
n % 4 != 0Why It Works
每一回合最多可以拿 3 个石头，而两个人合起来可以被控制成一组 4：
我拿 m 个，对方拿 4 - m 个或者反过来：
对方拿 m 个，我拿 4 - m 个因为 m 只能是 1、2 或 3，所以 4 - m 也一定是 1、2 或 3，是合法操作。
当某个人面对 4 个石头时：
- 他拿
1，对方拿3 - 他拿
2，对方拿2 - 他拿
3，对方拿1
对方总能拿完最后的石头。因此 4 是必败局面。
同理，8、12、16 这些 4 的倍数，也都是必败局面。因为只要当前玩家打破这个倍数，对方就可以补回一组 4。
所以：
n % 4 == 0：先手必败n % 4 != 0：先手可以先拿走余数，把必败局面交给对方
Code
def canWinNim(n):
return n % 4 != 0Complexity
| Time | \(O(1)\) - 只做一次取余判断 |
| Space | \(O(1)\) - 不需要额外数据结构 |
Takeaway
博弈题不一定要模拟所有选择。先找小数字里的必败局面，再观察周期。如果每轮双方的操作可以被控制成固定总数，就可以用取余直接判断胜负。
← Quiz