题目描述
你和你的朋友,两个人一起玩 Nim 游戏:
桌子上有一堆石头。
你们轮流进行自己的回合,你作为先手。
每一回合,轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数,来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢,返回 true;否则,返回 false 。
样例
输入:n = 4
输出:false
解释:如果堆中有 4 块石头,那么你永远不会赢得比赛;
因为无论你拿走 1 块、2 块 还是 3 块石头,最后一块石头总是会被你的朋友拿走。
算法1
(sg函数) $O(n)$
使用sg函数在数字较大时,容易爆栈
C++ 代码
class Solution {
public:
unordered_map<int, int> f;
int sg(int x)
{
if (f.count(x))
return f[x];
unordered_set<int> S;
for(int i = 1; i <= 3; i++)
{
if(x >= i)
{
S.insert(sg(x - i));
}
}
for (int i = 0; ; i++)
{
if (!S.count(i))
{
f[x] = i;
return i;
}
}
}
bool canWinNim(int n) {
return sg(n) == 0? false: true;
}
};
算法2
(数学) $O(1)$
由于此题所做的操作为减1-3个石子,相当于可以取走模4后剩余的数,因此只要我方先取走模4后剩余的数则必胜,否则必败。
C++ 代码
class Solution {
public:
bool canWinNim(int n) {
return n%4?true:false;
}
};