你和你的朋友，两个人一起玩 Nim 游戏：
- 桌子上有一堆石头。
- 你们轮流进行自己的回合，你作为先手。
- 每一回合，轮到的人拿掉 1 – 3 块石头。
- 拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
示例 1：
输入：n = 4
输出：false
解释：如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。
示例 2：
输入：n = 1 输出：true
示例 3：
输入：n = 2 输出：true
提示：
1 <= n <= 231 - 1
Related Topics
今天每日一题
class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}为啥是4呢？首先我们假设有A、B俩人，每个人分别可以拿走1到3个石头，不能不拿，我们按照两人都拿一次作为一轮，那么有以下几种情况。
A拿了1个，B可以拿1、2、3个，一轮可以拿走2、3、4个石头
A拿了2个，B可以拿1、2、3个，一轮可以拿走3、4、5个石头
A拿了3个，B可以拿1、2、3个，一轮可以拿走4、5、6个石头
那么可以看到，无论A拿走几个石头，B都可以拿走对应的不同数量来使得本轮一共拿走了4个石头。在这样的情况下，如果桌上石头总数一开始是4的倍数。则B稳赢。
如果一开始不是4的倍数，则A先手的情况下可以拿走对应的数量使得桌面上的石头数量变成4的倍数，这时候B再拿石头，则A稳赢。
所以只要桌面上石头的数量是4的倍数，先手的人一定会输，而如果不是4的倍数，先手的人可以拿走对应的数量使得变为4的倍数，这时候轮到另一个人，则另一个人会输。
因为题面中给定了一个条件
假设你们每一步都是最优解那么表示两个人都知道要往4个这个数量上来凑。
发表评论