題目:

You are playing the following Nim Game with your friend:

Initially, there is a heap of stones on the table.
You and your friend will alternate taking turns, and you go first.
On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
The one who removes the last stone is the winner.

Given n, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.

你和朋友在玩一個叫Nim Game的遊戲,規則如下:
1.有一疊石頭,兩人輪流,一個人一次能移開1~3個石頭,最後把石頭拿完的人勝利
2.你是先手
題目會給定一數n表石頭數,若在兩人都認真玩遊戲的情況下
你能贏這場遊戲的話回傳True,反之回傳False

我還蠻喜歡這題的
很像小時候玩的機智問答

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n%4

我們知道當石頭只有4顆且我們先手時是必輸之局
我取1朋友取3,我取2朋友取2,我取3朋友取1不管怎樣都輸
所以我們要營造輪到朋友時石頭剩4顆的情境我們才會贏
而只有在石頭不是4的倍數時,我們才能營造出這種情境

1.石頭為4的倍數:
我們拿x顆,朋友只要拿4-x顆就能維持石頭是4的倍數
直到石頭是4顆時我們會是先手,所以必輸
2.石頭不為4的倍數:
我們只要一開始拿掉n%4的石頭就能讓朋友掉進1.的循環,所以必贏

所以這題只要判斷n是否為4的倍數即可
最後執行時間32ms(faster than 90.66%)

那我們下題見