Leetcode第95場比賽回顧
零、背景
這週五團隊一起做了 Leetcode 第 95 場比賽。
做到第二題，我就發現很多人可能到這裡就不會了。
做第三題時，我剛開始完全沒想法，是先跳過去做第四題的，最後有想法了才把第三題幹掉的。
現在來看下比較有難度的一場比賽吧。
PS：這次比賽我是第一次直接在瀏覽器上做題的，沒想到瀏覽器上敲程式碼這麼方便。
正常比賽下來，只用了一點小時多一點。
明天又比賽了，我再嘗試在瀏覽器上做題試試。
一、連結串列的中間結點
題號：876
題目：Middle of the Linked List
題意：輸出連結串列的中位數。 如果有兩個（偶數長度），輸出後面那個。
思路：最簡單的方法就是先迴圈求出連結串列的長度，計算出答案的位置，然後迴圈找到那個位置即可。
可以看到，這樣需要迴圈兩次才能找到答案。
另一種更快的方法是使用快慢指標，這樣迴圈一遍就可以找到答案了。
二、石子游戲
題號：877
題目：Stone Game
題意：N堆石頭排成一行， Alex 和 Lee 兩個人輪流拿走一堆石頭。
問最終第一個人 Alex 拿到的石頭是否可以比第二個多。
規則：有偶數堆石頭，每次只能從兩頭來選一堆。
思路：第一眼看到這道題，我們可以確定這是一道博弈題。
但是不能直接根據遞迴的子狀態來判斷是否能贏。
我們只能做到求出子狀態的最優值，返回給當前狀態，然後求出當前狀態的最優值。
以 p[1] p[2]... p[n-1] p[n] 為例。
當前狀態是 1~n ， Alex 的目標是在 1~n 的兩邊選擇一堆石頭，使得自己的總石頭數量最大，我們稱為 f(1,n) 。
當 Alex 選擇 p[1] 時， Lee 肯定會盡使自己的石頭數最大，即 f(2,n) 。
此時 Alex 的石頭總數是 sum(1,n) - f(2,n) 。
當 Alex 選擇 p[n] 時， Lee 的選擇則是 f(1,n-1) 。
此時 Alex 的石頭總數是 sum(1,n) - f(1,n-1) 。
面對這兩種選擇， Alex 肯定選擇兩個結果裡最大的選擇。
分析到這裡，我們也就把這個博弈過程講清楚了。
具體用程式碼實現就是一個 DFS 。
而考慮到子狀態存在重複計算，則需要記憶狀態。
當然，這兩個結合起來，其實就是動態規劃了。
賽後，大家討論的時候，一個同學說：我沒找到 Alex 失敗的情況，於是直接提交 Alex 永遠成功，想看看反例是什麼。結果提交後這道題就過了。
然後也有幾個同學說自己的演算法敲錯了，最終也都過了。
那為什麼會這樣呢？
後來我想了想，想明白了為什麼 Alex 必勝 Lee 必敗。
而且道理也很簡單，不信你看。
總共有偶數堆石頭，石頭總個數是奇數個。
這說明最終肯定有一個人勝出。
偶數堆按奇偶性分別求和，則要麼偶數堆大，要麼奇數堆大。
假設石頭堆是 1 ~ 2n 。
如果偶數堆大，則 Alex 選擇 p[2n] 這堆石頭， Lee 只能選擇 p[1] 或 p[2n-1] ，即只能選擇奇數堆。
之後 Alex 依舊是選擇偶數堆，而 Lee 只能選擇奇數堆。
最終， Alex 選擇的都是偶數堆， Lee 選擇的都是奇數堆，這樣 Alex 就比 Lee 選的多了。
而對於奇數堆大，是一個道理。
所以第一個選擇的人 Alex 必勝了。
這道題算是有史以來程式碼最短的題了，只需要 return true; 即可。
三、第 N 個神奇數字
題號：878
題目：Nth Magical Number
題意：如果正整數可以被 A 或 B 整除，那麼它是神奇的。 返回第 N 個神奇數字。
規則：由於答案可能非常大，返回它模 10^9 + 7 的結果。
思路：看到這道題的第一眼，我是一臉懵逼的，於是就先做下一道題了。
下一道題做完後，只剩這一道題了，就只能分析這道題的特徵了。
一分析不要緊，還真找到一個規律：神奇數是有周期的，週期就是 A和B的最小公倍數。
假設 A 和 B 的最小公倍數是 G，其中有 m 個神奇數，分別表示為 f[1],f[2]...f[m] 。
則第 m+1 個神奇數肯定是 G + f[1] ，而第 m + 2 個神奇數肯定是 G + f[1] 。
推廣就是，第 N 個神奇數是 G * (N/m) + f[N%m] 。
那接下來的問題就是：怎麼求最小公倍數以內的所有神奇數？會不會很多？會不會超時？
面對發自內心的三連問，我想先解決第一個問題：先寫出程式碼提交了再說。
寫了一個迴圈就求出了所有的神奇數，提交後就過了。
然後我思考：為什麼沒超時？會不會本來就不多？怎麼證明？
面對接下來的三連問，其實是一個問題：怎麼證明公倍數內的神奇數不多。
簡單一思考，發現很容易證明。
與 A 有關的神奇數是 A,2A,...,BA 。
與 B 有關的神奇數是 B,2B,...,AB 。
這樣合起來神奇數最多就是 A+B-1 個。
在考慮公約數的問題，神奇數還會比這個還少，即只有 G/A + G/B - 1 個。
而 A 和 B 只有幾萬，複雜度可以接受，所以這樣做不會超時，證閉。
四、盈利計劃
題號：879
題目：Profitable Schemes
題意：有 G 個人，有多起犯罪同時發生。
每個犯罪需要 group[i] 個人，可以獲取 profit[i] 的利潤。
統計到犯罪至少獲取的利潤是 P,問可能有哪些犯罪發生。
思路：只要題意看懂，就可以看出這是一道基本的動態規劃題，甚至是揹包問題的變種。
直接把涉及到的變數組裝起來，就可以表達出狀態： f(G, P, n) 。
含義是前 n 起犯罪裡不超過 G 人時至少獲得利潤 P 的情況數。
此時對第 n 起犯罪分情況討論。
如果參與犯罪（前提是能），則狀態轉化為 f(G-g[n], P-p[i], n-1) + check(p-p[i]) 。
check 的含義是到目前未知，利潤是否已經夠了，夠了就算一個答案。
如果不參與犯罪，則狀態是 f(G, P, n-1) 。
就這樣，就可以求出答案來，複雜度 O(n^3)
五、最後
這次比賽其實蠻有難度的。
除了第一題是水題，第二第四是動態規劃，第三是數學題，一般人面對這三道題都會是一道坎。
除非你非常聰明，一般人都需要大量的訓練才能熟練的掌握這些題型的。
當然，第二題其實不好，很多人程式碼敲錯了都水過去了。剛才我看了下我的程式碼，有個地方敲錯了，少了個逗號，也過了。
PS：最近我在想怎麼把自己做過的題組織起來，以供大家搜尋、分類，從而方便的進行專項練習。
目前的選擇有兩種，一種是在我的網站上實現這個功能，一種是使用知識星球的標籤功能，大家怎麼看這個呢？
-EOF-