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.
尼姆游戏：有一堆石子，每次只能从里面拿出1~3块。谁拿到了最后一块谁赢。你先拿。两个人都很聪明，都知道怎样能赢。设计一个函数检测对于给定的石子数，你能否赢得比赛。

算法分析：

方法一：

如果最后剩下4个石子，后拿的那个人赢。因此如果是4的倍数，你先拿x，后拿的人取4-x，因此后拿的那个人赢。

Java代码

public class Solution {
    public boolean canWinNim(int n) {
        if (n % 4 == 0) return false;
        else return true;
    }
}

方法二

与方法一类似，通过移位来判定是否是4的倍数，不是，就能赢。

Java代码

public class Solution {
    public boolean canWinNim(int n) {
        if (n <= 0) return false;
        
        return n>>2<<2 != n;
    }
}

参考

LeetCode
oschina
维基百科