leetcode-292-Nim-Game

描述


You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

分析


博弈论经典模型,这里,任何一方,不管是先取后取得,要想赢,取得时候使得剩下的石子能被4整除,这样最后剩4个,对方先取,一定能赢。所以这里的石子只要不能被4整除,先取得一定能赢。

解决方案1(C++)


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

在评论区里有一种hack的做法:

1
2
3
4
5
6
class Solution {
public:
bool canWinNim(int n) {
return (n&3) != 0;
}
};

不能被4整除的话,通过2进制的与运算,结果必然不为0,返回这一判断即可。

解决方案2(Python)


1
2
3
4
5
6
7
class Solution(object):
def canWinNim(self, n):
"""
:type n: int
:rtype: bool
"""
return n&3 != 0

相关问题


(M)-Flip-Game-II

题目来源