LeetCode值Nim Game

周末刷知乎的時(shí)候，有人說leetcode.com網(wǎng)站上的練習(xí)題非常適合準(zhǔn)備跳槽的人，雖然我不準(zhǔn)備跳槽，但多見識一些總沒有錯，抱著好玩的心態(tài)，按照難度的排了順序，開始做題。

這就是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.

這個(gè)題大家想必都不陌生，大致題意是，你和你的一個(gè)朋友玩游戲，且你和你的朋友足夠聰明，規(guī)則是：有N個(gè)石子，每人每次可以拿走1-3個(gè)石子，拿走最后那一個(gè)石子的人獲得勝利，且你是第一個(gè)去取石子的人。請寫一個(gè)函數(shù)，當(dāng)輸入正整數(shù)n時(shí)，返回值為你是否獲勝，true為獲勝，false為失敗。

舉例，如果這里有4個(gè)石子，那么你將會輸?shù)粲螒?，因?yàn)闊o論你移除1或2或3個(gè)石子之后，最后的石子都會被你的朋友拿走。

規(guī)則以及解題要求都已經(jīng)清楚了，那么下面我來講一下這道題的關(guān)鍵點(diǎn)：一、你和你的朋友足夠聰明；二、每人每次只能拿1-3個(gè)；三、當(dāng)N為4時(shí)，你一定是失敗的。

對數(shù)字敏感的同學(xué)應(yīng)該已經(jīng)看出端倪了，這是一道很簡單的算法題，所以就直接公布答案了：當(dāng)N > 0 and N < 4時(shí)，返回true;當(dāng)N > 4 且 N % 4 的值不為零時(shí)，返回值為true，否則返回false。意思就是，除了n為4的倍數(shù)以外的情況你會輸，其他情況你都是可以贏的。

這里說一下思路，因?yàn)楫?dāng)余數(shù)為1-3時(shí)，你可以將場面控制成剩余石子數(shù)為4的倍數(shù)。

PS：老話說的話，先下手為強(qiáng)吶！