题目描述
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.
Example:
Input: 4 Output: false Explanation: 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 emoved by your friend.
解题思路
- 如果是4的话 谁先拿谁输 第一个人拿n个，第二个人拿 4 - n个
- 如果是1-3 肯定是第一个人获胜
-
5，6，7我们可以剩余4个的倍数，然后对方再拿，就变为输
- 参考这里
- 从1开始，多枚举几次就能发现规律。
- 石头个数是1、2、3的时候，我是获胜者。
- 4的时候对方是获胜者。
- 5、6、7个石头的时候，我只要拿走1个石头，就变成4个石头而且是对手先拿的情况，那么我就是获胜者。
- 8个石头的时候，我无论拿几个石头，对手都能变到4个石头我先拿的情况。
- 这样下去，不难发现只要是4的倍数，对手就赢。所以只要判断是不是4的倍数就可以了。
class Solution {
public:
bool canWinNim(int n) {
return n % 4;
}
};
