LeetCode刷題之292. Nim 遊戲

我不知道将去向何方，但我已在路上！
時光匆匆，雖未曾謀面，卻相遇于斯，實在是莫大的緣分，感謝您的到訪 ！

• 題目：

你和你的朋友，兩個人一起玩

Nim 遊戲

：

- 桌子上有一堆石頭。
- 你們輪流進行自己的回合，你作為先手。
- 每一回合，輪到的人拿掉 1 - 3 塊石頭。
- 拿掉最後一塊石頭的人就是獲勝者
           

假設你們每一步都是最優解。請編寫一個函數，來判斷你是否可以在給定石頭數量為

n

的情況下赢得遊戲。如果可以赢，傳回

true

；否則，傳回

false

。

• 示例：

示例 1 :
輸入：n = 4
輸出：false 
解釋：如果堆中有 4 塊石頭，那麼你永遠不會赢得比賽；因為無論你拿走 1 塊、2 塊 還是 3 塊石頭，最後一塊石頭總是會被你的朋友拿走。
           

示例 2 :
輸入：n = 1
輸出：true
           

示例 3 :
輸入：n = 2
輸出：true
           

• 提示：

  • 1 <= n <= 2^31 - 1

• 代碼1：

class Solution:
    def canWinNim(self, n: int) -> bool:
        if n % 4 == 0:
            return False
        else:
            return True
           

• 算法說明：

  巴什博奕， n % ( m + 1 ) ! = 0 n\%(m+1)!=0 n%(m+1)!=0 時，先手赢（n是總數，m是每次拿到的最大個數）。