演算法學習之 Leetcode 破關總指南（三）

進階訓練、特殊題型、挑戰極限！

Building photo created by liuzishan — www.freepik.com

上一篇，我們進入了實戰訓練，也介紹了不同難度的訓練方式，現在的你，可以更進一步挑戰極限了。

資料結構練功坊 LV. 2

從這裡開始，觀念的難度會上升一個層級，每個主題都可以想成一個遊戲中的小 boss，可能光看懂教學解說都需要費一番功夫，但這邊也是真正實力差距的開始，要想進 Top 公司，以下才是見證真功夫的時刻。

這區域中會出現一些較複雜的資料結構，或舊資料結構的進階應用，通常有以下這些主題，部分主題一樣可以看 Hackerearch 的介紹，或看我下面找到的連結。

1. Monotonic Stack/Queue
2. Tree (Binary Tree & Binary Search Tree)
3. Graph
4. Heap (Priority Queue)
5. Union Find (Disjoint-set)
6. Design（要你設計指定特殊要求的資料結構）
7. Trie

一樣學習方式還是一個一個主題，找能讓你看懂的教學文章、影片、課程，看懂後去 Leetcode 上面找對應的標籤實戰練習基本型，儘量找一些貼近觀念基本型的題目，其難度大多都在 Medium（少數 Easy），而 Hard 一樣可以先不要碰，因為 Hard 題通常不止要應用這些概念，還得多轉很多彎，或結合其他概念，這種我們留待之後再來挑戰。

還有一個簡單判斷法是看一下 討論區，如果最高 voted 的解釋也是寫的落落長還圖文並茂，大概都要轉很多彎才能解，那就先跳過。

以下精選幾個適合練習的好題目

1. Monotonic Stack/Queue: Final Prices With a Special Discount in a Shop
2. Tree:
   Insert into a Binary Search Tree
   Construct Binary Tree from Inorder and Postorder Traversal
3. Graph: Keys and Rooms
4. Priority Queue: Last Stone Weight
5. Union Find: Number of Provinces
6. Design:
   Min Stack
   Design Circular Queue
7. Trie: Implement Trie (Prefix Tree)

演算法練功坊 LV. 2

如同上面的資料結構 LV2，這邊則是一個個進階演算法，通常有以下主題

1. Backtracking
2. Shortest Path in a Graph
3. Greedy（Advanced）
4. Dynamic Programming
5. Bit Manipulation（Advanced）

或建構在特定資料結構上的演算法

1. Dijkstra: Graph + Priority Queue
2. Topological Sort: Graph
3. Minimum Spanning Tree: Graph + Union Find
4. Tree 的 LCA, 各式 DFS Traversal 轉換應用等等

對於這種較進階演算法的學習步驟，通常如下

1. 搜尋關鍵字，找一個教材努力看懂他的概念
2. 先自己嘗試實作出這個概念的原型
3. 看教學寫的標準寫法，跟你上一步自己實作出來的做個比較，通常在比較複雜的演算法中，程式寫法的重要性有時候不下於概念本身，一個精簡好懂的寫法，可以幫助你記憶，且大幅減少 bug，面試時才有可能做出來
4. 去找 Leetcode 的基礎題，驗證你寫好的這個模板跑起來正確無誤
5. 找這個 Tag 底下的其他問題，一樣先以 Medium 為主，測試自己能不能看出來如何使用該演算法解題

以下分享一些非常適合做驗證練習用的基礎題

1. Backtracking: Combinations
2. Dijkstra: Network Delay Time
3. Topological Sort: Course Schedule II
4. Greedy（Advanced）:
   Gas Station
   Non-overlapping Intervals
5. DP:
   Unique Paths
   Coin Change
   Edit Distance
6. Bit Manipulation（Advanced）: Maximum XOR of Two Numbers in an Array

一樣用遊戲比喻的話，這個區域練的都是一些進階招式，變化當然也會很大，所以要有心理準備，學習時間也會比之前都長，需要很多時間反覆沉澱思索咀嚼，才能內化成你自己的東西。建議是前面區域基本功的熟練度足夠再來挑戰，比較不會一直卡死太過痛苦而決定放棄。

但即使變化大，仍然是有跡可循，我們一樣可以採取一個一個關鍵字搜尋教學，之後上 Leetcode 找對應的練習題的策略，只是範圍更廣了些。

而其中最惡名昭彰的是 Dynamic Programming（DP），變化極為繁多，雖然都有一致的策略跟思考方向在，但每種新變化型都不容易在完全沒看過的狀況下憑空想出來，所以等於光他一個，就又可以拆成好幾個獨立的演算法來學了（常見的型大概就有 7, 8 種之多）。如果覺得學起來很痛苦，可以看看我另外以動態規劃為主題寫的系列文。

從零開始進入動態規劃的世界（一）- 基礎中的基礎

好消息是一般公司大概也不太敢去考太複雜的 DP 題目，頂多考經典型（太難的面試官都不一定會？），但如果目標是世界頂尖 Tier 1 公司，由於前面稍容易的問題競爭者們都會做，所以困難 DP 往往變成拿來最終鑑別實力的題，有志者不能輕易放棄。

實戰應用練習場 LV. 2

最後，最難的地獄關卡就是這了，光是你能走到這步，應該已經具備應付大多數公司演算法考題的實力了，在 Leetcode 週賽通常也能穩定解 2 ～ 3 題。但如果還想往前走，這邊會是一大難關，就是以上所有東西的靈活變化應用。

如同實戰應用練習場 LV1，這邊的題都會藏的比較深，初看題目通常第一時間只能發愣，想不到這鬼東西該如何下手，但如果你上面幾個區的東西都能確實掌握好，現在就是大考驗的時刻。由於 Leetcode 的範圍還算很有限（跟競賽型的 Competitive Programming 相比），所以通常一定會是某個你前面章節學過的東西。

這邊的題目，一般要去每個 tag 的 Hard 題找，一樣先從讚數最多的做起，後期可以打週賽挑戰時限內做出第四題。而剛開始如果感覺每一題都做不出來，是非常正常的，不用灰心。由於到這區的你，已經具備一定的程度了，當我們想不出來，可以用以下的方式去看討論區學習

1. 開討論區，看 voted 最高的解釋，但不要全部看完（也可以看 Leetcode 題目的官方提示，意思差不多）
2. 通常你會先看到關鍵字，是你前面學過的概念，這時候可以先關掉解答，回來想想該觀念要怎樣套到這題上面來
3. 如果仍然卡關，再開討論區續看，但一樣如果看他到講了某個關鍵思路，是你之前沒想到的，而且讓你有一點點感覺，好像有點想法了。那一樣關掉解答，重新回來自己想想
4. 如果仍然卡關，才回去把整份討論區解答看完，然後好好沉澱想想這整題當中，有哪些觀念是你之前完全沒想過的，這就成為了你的養分，恭喜你，又掃出一個盲點並克服他了

另外，到了這個等級，除了理解每個演算法的邏輯之外，最好也對實作方式有自己的一套系統了。這套系統會幫主你在面對那些需要多種技巧組合的難題很有幫助，避免你發生一些微小的 bug 而導致全盤出錯。

很多知名演算法，例如 Binary Search, Quick Sort, Dijkstra, … 等等，都可以找到幾個不同版本的寫法，最好讓自己理解每套寫法的邏輯，並選擇套最習慣的寫法，有一個習慣的模板，即使你疲累或緊張之下也不會出錯。

但習慣相同寫法後，也很容易陷入”套模板”解題的思維陷阱，結果久而久之太過習慣，碰到一些比較精彩的變化題突然就不會寫了，例如以下這題就是很經典的 Dijkstra 變型題，他要找的是第二短的路徑。

Second Minimum Time to Reach Destination

如果你只會背模板，應該很難寫出來，但如果你對 Dijkstra 的運作機制非常清楚，應該不難想到怎樣改寫他。

總而言之，這區將需要更多的時間磨練，假如能站穩，你應該多數時候都能在週賽解完四題，甚至提早很多時間完成，排名進入 1～5%，算是完全具備挑戰 Top Tier 公司的水準了，演算法考試也即將要成為你面試中最不害怕的一環了。

特殊挑戰

最後，還有一些在 Leetcode 比較罕見的題目類型，主題龐雜但每個遇到機會又都很低，以下舉幾個例子

1. Number Theory：各種需要先具備某些數論概念的題目，例如質數、最大公因數、或對某些數字的特殊性質觀察等等。這是筆者最苦手的類型，還好面試中出現機率也非常低。
2. 其他數學相關的獨立主題們：Geometry、Statistics and Probability、Game Theory、Bit Manipulation 等等。
3. Fenwick Tree & Segment Tree：需多次對 Array 做 range update & query 時使用（例如不停改變 Array 的內容，並一直問你不同範圍內的值加總是多少）。這是個競賽比較會出現的東西，但懂這技巧，有時候一些 Leetcode 難題靠他會突然變得很簡單。經典例子如 315. Count of Smaller Numbers After Self。
4. SortedContainer：基本上就是一個實作了紅黑樹的資料結構，具備可在 log(N) 時間內做到 insert/delete/search 的優良性質，雖然不太可能叫你當場寫一顆紅黑樹出來，但有少數難題可以靠 lib 內建的 SortedContainer 幫你解決，所以最少要會用，能懂背後運作機制當然更好。上面提到的 Leetcode 315 一樣靠他就會變簡單題了。
5. Graph 的其他經典進階演算法（但在 Leetcode 較少出現），例如 Minimum Spanning Tree、Bellman-Ford、Bipartite Graph、BCC/SCC、2SAT、Bridge、Articulation Point、Eulerian Circuit、Hamiltonian Path、Max-Flow/Min-Cut … 等等，種類繁多，且每一個難度都不下於 Dijkstra。
6. Interactive：互動題目，Leetcode 的通常不難，但寫法較為特別，可以認識一下。筆者自己就在面試 Google 時被考了一題這種風格的題目。
7. 還有奇怪主題如 SQL、shell 這些，一般是極少看到，要的話也是另外準備，Leetcode 還是以準備資料結構跟演算法的題目為主。
8. Concurrency：需要使用 multi-thread 工具去做的題目，雖然筆者自己覺得這已經脫離資料結構與演算法的範疇了，但網路上有看過文章說有被 FAANG 公司考過。而知名 Youtube Terry 也曾用過類似題目拍過實戰模擬面試的介紹影片，有興趣可以看我寫的這篇分析。

也給大家一些實際例子

1. Bit Manipulation: Single Number II（Bit Manipulation 進階）
2. Number Theory: Count Primes（質數基本題）
3. Segment Tree: Range Module（很難搞的區間維護，但用 Segment Tree 就變 Easy 題了）
4. Graph 進階：Reconstruct Itinerary（Eulerian Circuit 基礎概念）
5. Interactive: First Bad Version

這些準備起來較雜亂，遇到機會也少，我會建議留給上面都已經準備的很充分的人，想確保萬無一失，才去針對這些題目再下苦工。這邊也是這系列的結尾啦，如果能做到這個程度，相信你應該對自己非常有自信了，除非你想成為競賽選手，不然已經準備非常足夠了，軟體工程的領域如此浩大，帶著這個精神，把時間好好花在其他地方上面吧！祝各位武運昌隆。