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.

翻譯

拿石頭遊戲規則，桌上有石頭n個，兩個玩家，你先玩，每次每個玩家可以拿走1~3個石頭，拿走會後一顆石頭的人獲勝，根據以上規則與初始的石頭數量，判斷你是否能贏得這個拿石頭遊戲。

例如說，如果桌上有三顆石頭，你一次全拿，獲勝。
如果桌上有4顆石頭，不管你拿走幾顆，你的對手都會獲勝。

思路

考慮到下面幾總情況

1. 石頭數量小於等於3，直接獲勝
2. 石頭數量等於4個，輸
3. 石頭數量5個，先拿走1個，獲勝
4. 由以上可以推論(5-1=4, 6-2=4, 7-3=4) 5~7都可以獲勝
5. 石頭數量8個，不管怎樣都會輸

以上可以得到結論，只要一開始的石頭數量為4的倍數，就會輸。

解題

var canWinNim = function(n) {
    // 4個以下，全拿穩贏
    if(n < 4){
        return true;
    }
    // 4的倍數，穩輸
    return n%4 != 0;
};