打开 LeetCode 评论区，都在自嘲是智障！
多写、多练、多思考，持续输出第 6/10 天｜执行｜专注｜坚持
大家好，我是吴师兄。
昨天那篇 反响很好，所以今天继续分享 LeetCode 上比较有意思的问题或者回答，闲暇之余，博君一笑。
这道题目是 LeetCode 第 292 号问题 Nim 游戏。
打开 LeetCode 评论区，有不少人都在感叹：我是傻子！
依旧先给没有有见过这道题目的小伙伴补充一下前置知识，Nim 游戏 这道题目讲的是你和你的小伙伴两个人玩石头，每个人都可以在自己的回合里面选择拿掉面前的 1 块或者 2 块或者 3 块石头，轮流进行，最终拿掉最后一块石头的人就是获胜者。
并且，这个游戏的先手是你自己！
这里有个前提，你和你的小伙伴都是聪明人，也就是说都会思考怎么样才能赢得最后的比赛，不存在某人犯浑，让对方偷鸡。
题目需要我们去判断是否可以在给定石头数量为 n 的情况下赢得游戏。
大家的第一想法是什么？
我的想法是这是一道简单的动态规划题。
设置一个 dp 数组，dp[i] 表示石头数量为 i 的情况下先手的人是否可以赢得游戏。
初始化很容易想到，如果只有 1、2、3 块石头，先手的人都能赢得游戏。
dp[1] = true;
dp[2] = true;
dp[3] = true;
状态转移方程是这样思考得来的，面对 i 块石头，能否赢得游戏，取决于对手是否可以在剩下 i - 1、i - 2、i - 3 块石头时赢得游戏，对手不能我才能，对手能我就不能。
dp[i] = !dp[i - 1] || !dp[i - 2] || !dp[i - 3];
三下五除二，写完代码：
public class Solution {
public boolean canWinNim(int n) {
if ( n <= 3 ) return true;
// dp[i] 表示石头数量为 i 的情况下先手的人是否可以赢得游戏
boolean[] dp = new boolean[n + 1];
// 初始化
dp[1] = true;
dp[2] = true;
dp[3] = true;
// 填充 dp 数组
for (int i = 4; i <= n; i++) {
dp[i] = !dp[i - 1] || !dp[i - 2] || !dp[i - 3];
}
// 获取结果
return dp[n];
}
}
不愧是简单的动态规划题，轻轻松松写好，赶紧提交。
LeetCode 给我一个大棒子：超出内存限制。
LeetCode 咋这么穷呢？多给点空间不行么？
算了，改一下，复用一下空间。
public class Solution {
public boolean canWinNim(int n) {
if ( n <= 3 ) return true;
// dp[i] 表示石头数量为 i 的情况下先手的人是否可以赢得游戏
boolean[] dp = new boolean[4];
dp[0] = false;
dp[1] = true;
dp[2] = true;
dp[3] = true;
// 填充 dp 数组
for (int i = 4; i <= n; i++) {
// dp 数组就这么大，对 4 取余不断的覆盖之前的值，因为只需要知道最后的结果就行
dp[i % 4] = !dp[(i - 1) % 4] || !dp[(i - 2) % 4] || !dp[(i - 3) % 4];
}
// 获取结果
return dp[n % 4];
}
}
提交！
我以为是自己会员这两天到期的缘故，经过漫长的等待后：超出时间限制。
这就尴尬了，动态规划都不好使，咋搞。
打开评论区，好家伙，上当的人还不少！
“我大意了啊，没有多想，上来就是一个递归，一个贪心，一个规划，全都给我防出去了啊，来骗，来偷袭，我这个老同志，这好吗，这不好，出题人耗子尾汁，不要再犯这样的小聪明。
”
这原来是一道找规律题，大家都是聪明人，就我不聪明。
代码非常非常简单，核心代码就一行。
class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}
解释一下什么意思。
核心点就是在选择的时候需要能构造出最后的那堆石头剩下的数量必须是 1、2、3 块，你才能赢得游戏。
举几个例子。
当堆里剩下 1、2、3 块，你可以赢得比赛。
当堆里只剩下 5 块，你需要选择拿走 1 块，剩下 4 块，无论对手怎么选，都会给你留下 1、2、3 块石头，你可以赢得比赛。
当堆里只剩下 6 块，你需要选择拿走 2 块，剩下 4 块，无论对手怎么选，都会给你留下 1、2、3 块石头，你可以赢得比赛。
当堆里只剩下 7 块，你需要选择拿走 3 块，剩下 4 块，无论对手怎么选，都会给你留下 1、2、3 块石头，你可以赢得比赛。
由于你的对手也很聪明！
那么当堆里剩下 4 块石头时，你无论怎么选，都会给对手留下可以直接赢得游戏的数量，比如你选 1 块，对手选 3 块；你选 2 块，对手选 2 块；你选 3 块，对手选 1 块。
也就是说，对手想赢得游戏，会最终丢给你一堆包含 4 块的石头。
如果总的石头数目是 4 的倍数，无论你取多少石头，对手总有对应的取法，让剩余石头的数目继续为 4 的倍数。
上面这句话就是重点，因为你选 1 块，对手选 3 块；你选 2 块，对手选 2 块；你选 3 块，对手选 1 块，那么最终推到你面前的手头数量只是减少了 4 块，依旧可以让剩余石头的数目继续为 4 的倍数。
所以，如果总的石头数目是 4 的倍数，无论你怎么选择，都会输掉比赛！
那如果总的石头数目不是 4 的倍数呢？
你可以采取选完石头之后让剩下的石头数目为 4 的倍数的策略。
这样，无论对手怎么选，你都可以让剩余石头的数目继续为 4 的倍数，从而最终让对手面对只有 4 块石头的局面，你赢得了比赛。
这也就是这一行代码的具体含义。
class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}
立马提交。
牛逼，击败 100% ！
如果你之前没有接触过博弈论的题目，或者找规律的数学题，是很难想到这种解法的。
那怎么办呢？
评论区的老哥给出了答案，打表找规律。
你学会了么？