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塊。誰(shuí)拿到了最后一塊誰(shuí)贏。你先拿蔽豺。兩個(gè)人都很聰明籍茧，都知道怎樣能贏贤旷。設(shè)計(jì)一個(gè)函數(shù)檢測(cè)對(duì)于給定的石子數(shù)亲澡，你能否贏得比賽疼阔。
算法分析：
方法一：
如果最后剩下4個(gè)石子盲憎，后拿的那個(gè)人贏嗅骄。因此如果是4的倍數(shù)，你先拿x饼疙，后拿的人取4-x溺森，因此后拿的那個(gè)人贏。
Java代碼
public class Solution {
public boolean canWinNim(int n) {
if (n % 4 == 0) return false;
else return true;
}
}
方法二
與方法一類似宏多，通過(guò)移位來(lái)判定是否是4的倍數(shù)儿惫，不是，就能贏伸但。
Java代碼
public class Solution {
public boolean canWinNim(int n) {
if (n <= 0) return false;
return n>>2<<2 != n;
}
}
