讀完本文，你可以去力扣拿下如下題目：
292.Nim遊戲
877.石子游戲
319.燈泡開關
-----------
下文是我在 LeetCode 刷題過程中總結的三道有趣的「腦筋急轉彎」題目，可以使用演算法程式設計解決，但只要稍加思考，就能找到規律，直接想出答案。
一、Nim 遊戲遊戲規則是這樣的：你和你的朋友面前有一堆石子，你們輪流拿，一次至少拿一顆，最多拿三顆，誰拿走最後一顆石子誰獲勝。
假設你們都很聰明，由你第一個開始拿，請你寫一個演算法，輸入一個正整數 n，返回你是否能贏（true 或 false）。
比如現在有 4 顆石子，演算法應該返回 false。因為無論你拿 1 顆 2 顆還是 3 顆，對方都能一次性拿完，拿走最後一顆石子，所以你一定會輸。
首先，這道題肯定可以使用動態規劃，因為顯然原問題存在子問題，且子問題存在重複。但是因為你們都很聰明，涉及到你和對手的博弈，動態規劃會比較複雜。
我們解決這種問題的思路一般都是反著思考：
如果我能贏，那麼最後輪到我取石子的時候必須要剩下 1~3 顆石子，這樣我才能一把拿完。
如何營造這樣的一個局面呢？顯然，如果對手拿的時候只剩 4 顆石子，那麼無論他怎麼拿，總會剩下 1~3 顆石子，我就能贏。
如何逼迫對手面對 4 顆石子呢？要想辦法，讓我選擇的時候還有 5~7 顆石子，這樣的話我就有把握讓對方不得不面對 4 顆石子。
如何營造 5~7 顆石子的局面呢？讓對手面對 8 顆石子，無論他怎麼拿，都會給我剩下 5~7 顆，我就能贏。
這樣一直迴圈下去，我們發現只要踩到 4 的倍數，就落入了圈套，永遠逃不出 4 的倍數，而且一定會輸。所以這道題的解法非常簡單：
bool canWinNim(int n) { // 如果上來就踩到 4 的倍數，那就認輸吧 // 否則，可以把對方控制在 4 的倍數，必勝 return n % 4 != 0;}遊戲規則是這樣的：你和你的朋友面前有一排石頭堆，用一個數組 piles 表示，piles[i] 表示第 i 堆石子有多少個。你們輪流拿石頭，一次拿一堆，但是隻能拿走最左邊或者最右邊的石頭堆。所有石頭被拿完後，誰擁有的石頭多，誰獲勝。
假設你們都很聰明，由你第一個開始拿，請你寫一個演算法，輸入一個數組 piles，返回你是否能贏（true 或 false）。
注意，石頭的堆的數量為偶數，所以你們兩人拿走的堆數一定是相同的。石頭的總數為奇數，也就是你們最後不可能擁有相同多的石頭，一定有勝負之分。
舉個例子，piles=[2, 1, 9, 5]，你先拿，可以拿 2 或者 5，你選擇 2。
piles=[1, 9, 5]，輪到對手，可以拿 1 或 5，他選擇 5。
piles=[1, 9] 輪到你拿，你拿 9。
最後，你的對手只能拿 1 了。
這樣下來，你總共擁有 2 + 9 = 11 顆石頭，對手有 5 + 1 = 6 顆石頭，你是可以贏的，所以演算法應該返回 true。
你看到了，並不是簡單的挑數字大的選，為什麼第一次選擇 2 而不是 5 呢？因為 5 後面是 9，你要是貪圖一時的利益，就把 9 這堆石頭暴露給對手了，那你就要輸了。
這也是強調雙方都很聰明的原因，演算法也是求最優決策過程下你是否能贏。
這道題又涉及到兩人的博弈，也可以用動態規劃演算法暴力試，比較麻煩。但我們只要對規則深入思考，就會大驚失色：只要你足夠聰明，你是必勝無疑的，因為你是先手。
boolean stoneGame(int[] piles) { return true;}這是為什麼呢，因為題目有兩個條件很重要：一是石頭總共有偶數堆，石頭的總數是奇數。這兩個看似增加遊戲公平性的條件，反而使該遊戲成為了一個割韭菜遊戲。我們以 piles=[2, 1, 9, 5] 講解，假設這四堆石頭從左到右的索引分別是 1，2，3，4。
如果我們把這四堆石頭按索引的奇偶分為兩組，即第 1、3 堆和第 2、4 堆，那麼這兩組石頭的數量一定不同，也就是說一堆多一堆少。因為石頭的總數是奇數，不能被平分。
而作為第一個拿石頭的人，你可以控制自己拿到所有偶數堆，或者所有的奇數堆。
你最開始可以選擇第 1 堆或第 4 堆。如果你想要偶數堆，你就拿第 4 堆，這樣留給對手的選擇只有第 1、3 堆，他不管怎麼拿，第 2 堆又會暴露出來，你就可以拿。同理，如果你想拿奇數堆，你就拿第 1 堆，留給對手的只有第 2、4 堆，他不管怎麼拿，第 3 堆又給你暴露出來了。
也就是說，你可以在第一步就觀察好，奇數堆的石頭總數多，還是偶數堆的石頭總數多，然後步步為營，就一切盡在掌控之中了。知道了這個漏洞，可以整一整不知情的同學了。
三、電燈開關問題這個問題是這樣描述的：有 n 盞電燈，最開始時都是關著的。現在要進行 n 輪操作：
第 1 輪操作是把每一盞電燈的開關按一下（全部開啟）。
第 2 輪操作是把每兩盞燈的開關按一下（就是按第 2，4，6... 盞燈的開關，它們被關閉）。
第 3 輪操作是把每三盞燈的開關按一下（就是按第 3，6，9... 盞燈的開關，有的被關閉，比如 3，有的被開啟，比如 6）...
如此往復，直到第 n 輪，即只按一下第 n 盞燈的開關。
現在給你輸入一個正整數 n 代表電燈的個數，問你經過 n 輪操作後，這些電燈有多少盞是亮的？
我們當然可以用一個布林陣列表示這些燈的開關情況，然後模擬這些操作過程，最後去數一下就能出結果。但是這樣顯得沒有靈性，最好的解法是這樣的：
int bulbSwitch(int n) { return (int)Math.sqrt(n);}什麼？這個問題跟平方根有什麼關係？其實這個解法挺精妙，如果沒人告訴你解法，還真不好想明白。
首先，因為電燈一開始都是關閉的，所以某一盞燈最後如果是點亮的，必然要被按奇數次開關。
我們假設只有 6 盞燈，而且我們只看第 6 盞燈。需要進行 6 輪操作對吧，請問對於第 6 盞燈，會被按下幾次開關呢？這不難得出，第 1 輪會被按，第 2 輪，第 3 輪，第 6 輪都會被按。
為什麼第 1、2、3、6 輪會被按呢？因為 6=1*6=2*3。一般情況下，因子都是成對出現的，也就是說開關被按的次數一般是偶數次。但是有特殊情況，比如說總共有 16 盞燈，那麼第 16 盞燈會被按幾次?
16=1*16=2*8=4*4
其中因子 4 重複出現，所以第 16 盞燈會被按 5 次，奇數次。現在你應該理解這個問題為什麼和平方根有關了吧？
不過，我們不是要算最後有幾盞燈亮著嗎，這樣直接平方根一下是啥意思呢？稍微思考一下就能理解了。
就假設現在總共有 16 盞燈，我們求 16 的平方根，等於 4，這就說明最後會有 4 盞燈亮著，它們分別是第 1*1=1 盞、第 2*2=4 盞、第 3*3=9 盞和第 4*4=16 盞。
就算有的 n 平方根結果是小數，強轉成 int 型，也相當於一個最大整數上界，比這個上界小的所有整數，平方後的索引都是最後亮著的燈的索引。所以說我們直接把平方根轉成整數，就是這個問題的答案。