題目

你和你的朋友，兩個人一起玩 Nim 游戲：

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

假設(shè)你們每一步都是最優(yōu)解。請編寫一個函數(shù)，來判斷你是否可以在給定石頭數(shù)量為 n 的情況下贏得游戲。如果可以贏，返回 true；否則，返回 false。

示例 1：

• 輸入： n = 4
• 輸出： false
• 解釋： 以下是可能的結(jié)果:

1. 移除1顆石頭。你的朋友移走了3塊石頭，包括最后一塊。你的朋友贏了。
2. 移除2個石子。你的朋友移走2塊石頭，包括最后一塊。你的朋友贏了。
3. 你移走3顆石子。你的朋友移走了最后一塊石頭。你的朋友贏了。
   在所有結(jié)果中，你的朋友是贏家。

示例 2：

• 輸入： n = 1
• 輸出： true

示例 3：

• 輸入： n = 2
• 輸出： true

方法一：數(shù)學(xué)推理

思路及解法

讓我們考慮一些小例子。顯而易見的是，如果石頭堆中只有一塊、兩塊、或是三塊石頭，那么在你的回合，你就可以把全部石子拿走，從而在游戲中取勝；如果堆中恰好有四塊石頭，你就會失敗。因為在這種情況下不管你取走多少石頭，總會為你的對手留下幾塊，他可以將剩余的石頭全部取完，從而他可以在游戲中打敗你。因此，要想獲勝，在你的回合中，必須避免石頭堆中的石子數(shù)為 的情況。

• 我們繼續(xù)推理，假設(shè)當前堆里只剩下五塊、六塊、或是七塊石頭，你可以控制自己拿取的石頭數(shù)，總是恰好給你的對手留下四塊石頭，使他輸?shù)暨@場比賽。但是如果石頭堆里有八塊石頭，你就不可避免地會輸?shù)?，因為不管你從一堆石頭中挑出一塊、兩塊還是三塊，你的對手都可以選擇三塊、兩塊或一塊，以確保在再一次輪到你的時候，你會面對四塊石頭。顯然我們繼續(xù)推理，可以看到它會以相同的模式不斷重復(fù) ，基本可以看出如果堆里的石頭數(shù)目為 的倍數(shù)時，你一定會輸?shù)粲螒颉?/p>

• 如果總的石頭數(shù)目為 的倍數(shù)時，因為無論你取多少石頭，對方總有對應(yīng)的取法，讓剩余的石頭的數(shù)目繼續(xù)為 的倍數(shù)。對于你或者你的對手取石頭時，顯然最優(yōu)的選擇是當前己方取完石頭后，讓剩余的石頭的數(shù)目為 的倍數(shù)。假設(shè)當前的石頭數(shù)目為 ，如果 為 的倍數(shù)時，則此時你必然會輸?shù)粲螒?；如? 不為 的倍數(shù)時，則此時你只需要取走 個石頭時，則剩余的石頭數(shù)目必然為 的倍數(shù)，從而對手會輸?shù)粲螒颉?/p>

代碼

class Solution {
    func canWinNim(_ n: Int) -> Bool {
        return n % 4 != 0
    }
}

復(fù)雜度分析

• 時間復(fù)雜度：。

• 空間復(fù)雜度：。