LeetCode 292. Nim 游戏

题目链接

LeetCode 292. Nim 游戏

题解

其实是一道很简单的找规律啦,我在纸上推了一下就懂了。

$n$ 小于 $3$ 的话,不用说肯定是先手赢,一次就能拿完。

但是如果 $n$ 是 $4$ 的时候,先手无论怎么拿,最后一个都会被后手拿去。

你拿一个,后手拿三个;你拿两个,后手拿两个;你拿三个,后手拿一个。

ok,我们继续来看看,是不是所有 $4$ 的倍数都是这样呢?

拿 $8$ 举例,不论你拿多少个,对手总是可以把情况变得和 $4$ 块时一样:你拿一个,后手拿三个;你拿两个,后手拿两个;你拿三个,后手拿一个。这样只剩下 $4$ 个了,于是你又输了。

然后再推一下非 $4$ 的倍数的数个石头的情况就可以了。

最后的结论就是:如果 $n$ 是 $4$ 的倍数,先手会输。否则先手赢

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
bool canWinNim(int n) {
if (n % 4 == 0)
{
return false;
}
return true;
}
};

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×