如何有效地寫演演算法題

（點選上方公眾號，可快速關註）

來源：侯振宇 ，

www.cnblogs.com/sskyy/p/8268976.html

這篇文章最早發在我團隊的檔案中。我的團隊鼓勵每個同學都在業餘時間多做演演算法題，特別是新人。個人認為在程式設計能力的提升上比做 side project 更有用，對職業發展也是如此。當然出於興趣做的 side project 另當別論。轉到這裡，希望對各位讀者有用。

如何有效地寫演演算法題

目的

持續做演演算法題的目的仍然是自身能力提升。可以繼續細化成三點:

• 保持思維敏捷。非常重要，狀態好才能保持對程式設計的熱情。

• 對基礎的資料結構、查詢和排序保持熟練。能解決日常開發中的效能相關問題。

• 積累對問題域的探索。只有對問題域有足夠的探索，才可能舉一反三，迸發靈感。

方法

為了更有效地實現上面的標的。推薦用下麵的方式來做題:

嚴格使用番茄時鐘進行規劃

在刷題的過程中非常最容易產生挫敗感，無法堅持。原因是，長時間的思考導致疲倦，多次積累的疲倦使得自己產生了 抵觸記憶。以至於會下意識覺得做題就是 刻苦。

推薦大家在開始之前看看《意志力》。裡面指出 喜好 是會被記憶操控的，如果每次做一件事最後留下的映像都是輕鬆愉快的，那麼人就會越來越喜歡做此事，反之厭惡。所以為了能保持做題的興趣，務必每次要主動給自己留下好的記憶。

番茄時鐘能夠很好地保障不會出現 長時間 的思考，同時也能保障不容易 疲倦。如果你已經能很熟練的使用番茄時鐘，請跳過。如果你對番茄時鐘的印象仍然只是20分鐘休息一次。那麼請繼續閱讀。

番茄時鐘有兩個重點，一是透過長期的訓練，讓大腦習慣在一段時間內保持高效。二是透過要求每次在開始前有規劃和每次結束後有總結，保障產出。當把這兩點應用到做演演算法的過程中時，應該採取以下的方式：

用一個番茄時鐘對題目進行徹底的分析

目前 leetcode 上的題大致可分為兩種型別：

• 對某種複雜規則的徹底解析，很有可能要構造狀態機，充分考慮邊界情況。

• 對某種資料結構及演演算法的應用。

• 對數學概念、遍歷、動態規劃等的綜合應用。

在這個分析過程中首先要大致判斷出屬於哪一類。在掌握了基本的資料結構和演演算法後，應該能很好的判斷是不是屬於前兩類。如果判斷不出說明需要回頭先重新複習基本資料結構。推薦《演演算法》一書。不要強行刷題。演演算法書的每種資料結構及演演算法的大概思路、解決的問題以及相應的時間和空間複雜度瞭解之後可以再回來。

第一種情況

例子：https://leetcode.com/problems/valid-number/description/

這個番茄時鐘內的標的是：

• 理清題目背後解法要用的技術

• 充分收集可能涉及到的邊界

完成後應該有的總結是：

• 是否理清了要用的技術

• 是否有不確定的地方

• 收集到的邊界是否能改寫所有情況

如果發現在要用的技術中有不熟悉的地方，應該立即中斷，開啟另一個番茄時鐘進行學習。切忌盲目嘗試。當發現有不確定的地方時，重新開啟一個番茄時鐘，按照當前思路把不確定地方當成一個單獨的演演算法問題進行解決。

第二種情況

例子:https://leetcode.com/problems/reverse-pairs/

這一類題目通常採取遍歷的方法一定都能找到解法。重點是找到最優解，因此需要提前有足夠的資料結構的知識。資料結構可大致分為鏈(陣列、棧、佇列)、樹、圖。在這三類資料中要分別掌握排序和查詢演演算法。特別是相應的時間複雜度。

這類題目很好判斷，通常題目中會描述了幾個資料或者狀態的關聯的關係，然後需要你找出符合條件的某些資料。那麼將題目中的關聯關係轉換成相應的資料結構，再使用對應演演算法就夠了。要對資料結構的足夠熟悉，才能知道如何轉化。

這種情況下番茄時鐘的標的是：

• 將問題轉化為對相應資料結構的問題。

總結是：

• 需不需要分情況討論，需要一種資料結構還是多種

• 相應資料結構是否能完全改寫題目問題中的所有情況

第三種情況

例子：https://leetcode.com/problems/minimum-window-substring/

這一類情況最好用排除法，發現不是第一種或者第二種，那麼再往這種情況下考慮。這類題的特點是通常是發散性質，剛看到題目容易有思路，但不太容易找到最優解。這種情況下，也要先判斷題目子型別。

• 如果發現題目能從遍歷的角度解決問題，那麼可以往遍歷的最佳化上去想。例如是否在遍歷的時候能夠排除掉一些情況。或者透過排序等手段之後，能實現遍歷時排除某些情況。

• 如果發現題目中存在多種約束關係，然後求某個值，那麼可以往數學方程組上去想。

• 如果發現問題可以被遞迴解決，並且能夠將遞迴方式轉化成順序方式，可以往動態規劃上去想。

在這種情況下，番茄時鐘的標的：

• 判斷出題目型別。

總結：

• 是否有其他型別更適合。

• 是否需要多種手段結合。

執行時的番茄時鐘

當分析完之後，建議不要開始寫程式碼，一定要休息片刻。執行階段是對我們平時寫程式碼狀態的一種鍛煉，應該非常珍惜。如果一個番茄時鐘執行不完，應該拆分成多個。在這段時間中，設定的番茄時鐘標的應該是：

• 高效地驗證分析階段的思路

要實現執行高效，最重要的是養成良好的編碼習慣，不要犯小錯誤。要始終朝著只要想清楚了，一次寫好，不要除錯的狀態要求自己。這裡常見的小錯誤有：

• 拼寫錯誤。變數命名要足夠清楚，不要用單個字母或者語意不明的單詞。

• 陣列邊界未考慮。

• 空值未考慮。

• 用 Math.ceil 之類函式時未考慮清楚上下界。

除錯超過寫程式碼時間 30% 時說明狀態非常有問題。在這個階段的總結是：

• 是否完成了對分析的驗證

• 編碼過程是否足夠高效

如果中間發現了分析階段的錯誤或者疏漏。應該立即結束編碼，休息。並且重新開啟分析階段的時鐘。切忌邊寫邊改方案。如果發現編碼過程狀態不夠好，應該加長休息時間，或者乾脆結束掉。不要給自己留下低效的映像。將任務留到第二天其實也可以檢驗自己第一天的思路是否足夠系統化，如果是，那麼第二天應該能很快的重新找回思路。

任一番茄時鐘結束時

一定要做好總結，特別是當沒有解出題來，沒有思路的時候，一定要透過結束階段的總結來反思犯了什麼錯誤。解出來了也一定要總結題目的特點，題目中哪些要素是解出該題的關鍵。不做總結的話，花掉的時間所得到的收穫通常只有 50% 左右。

在題目完成後，要特別註意總結此題最後是歸納到哪種型別中，它在這種型別中的獨特之處是什麼。經過總結，這樣題目才會變成你在此問題域中的積累。

做好總結，讓每道題都有最大的收穫。一個月之後自己的狀態應該會有很大變化。

如何分享

在這個倉庫中進行解題分享時，建議大家就把自己番茄時鐘的執行記錄進行分享。最後標準的解法以及思路其實在 discussion 中都有。對他人有用的分享不是結果，而是：

• 你在番茄時鐘中是如何規劃的，也就是番茄時鐘的標的。

• 你是如何分析，也就是思路。

• 你的結論是什麼，或者是你在執行時除了什麼問題。

• 你所總結出的題目的關鍵部分。也就是對問題域進行探索的經驗。

看完本文有收穫？請轉發分享給更多人

關註「ImportNew」，提升Java技能