前言

看到 演算法學習之-Leetcode-破關總指南我覺得整理的非常好，準備開始作為之後刷LeetCode的指南。

本篇的所有內容非出自於我手，而是整理自 演算法學習之-Leetcode-破關總指南 的文章，我只是將他們的文章整理成一篇，方便之後查閱。

正確心態

  1. 不要硬去挑戰難題然後又硬要自己想出來才肯罷休，這樣的學習效率會很差，甚至學不到重點反而歪掉。好好把握你能抓得住的那一部分就好，吃不下去的就先放寬心不要著急。你的大腦仍然會或多或少的在背景運作吸收，並在未來的某一天有需要的時候，讓你想起來好像曾經聽過那個什麼，跟現在這件事有點關聯，但記不清楚了，只要這時候再重新好好補上就很完美了。
  2. 自己挑題目最重要原則：寧可太簡單，不要太難，太簡單還可以緩步提升難度，太難有可能一下把自己的正循環打斷，拖延症就容易趁機發作而不想學習，得不償失。
  3. 也不用太強求要把每個資料結構理解到最底層去，有大致理解他們各種操作的時間複雜度特性後，就可以先往下一關邁進了。
  4. 刷題順序
    1. 挑一個關鍵字找教材、影片或上課直到完全弄懂做法與時間複雜度的分析
    2. 去 Leetcode 找相同關鍵字的 Easy 題或簡單的 Medium 題，難易度可以用通過率 Acceptance 初步判斷，先不要碰 Hard
    3. 如果有做出來，繼續看他推薦的延伸題，一樣選 Easy 或簡單的 Medium
    4. 如果做不出來，回到步驟 1 看看還有哪邊沒懂，或去 Leetcode 討論區吸取他人經驗想法
  5. 如果在 Leetcode 討論區發覺大家講的做法太過神奇，與該演算法的概念已經關係不大，而是需要特殊技巧，那這題你暫時跳過也無妨，因為無助於現階段的學習。

新手村

  1. 輸入、輸出
  2. 整數、浮點數、字串、陣列、雙重陣列
  3. 判斷式 if / else
  4. 迴圈 for loop / while loop
  5. 函數 function()
  6. 變數值與記憶體位址的概念
  7. 十進位與二進位轉換的基本概念
  8. 時間複雜度、空間複雜度的基本概念與 Big-O Notation

資料結構L1

  1. Array
  2. Hash Table
  3. Set
  4. Stack
  5. Queue
  6. Linked List（先懂基本操作即可）
  7. Binary Tree（先懂基本 DFS/BFS 即可）

認識一個新資料結構，我們要關注的就是他各種操作的時間複雜度，最基本的操作如下:

  • insert
  • delete
  • find（找到某個值的位置）
  • peek（查看某位置的值）
  • check exist（確認值是否存在）

推薦題目

由於 Array 太過廣泛，幾乎任何題目都會用上，而 Queue 則是到後面 Tree 與 Graph 的章節才比較常用上，因此這邊先不特別列題目了。
以下來舉幾個基礎題的例子：

  1. Hash Table: Two Sum
  2. Set: Intersection of Two Arrays
  3. Stack: Valid Parentheses
  4. Linked List: Merge two sorted linked list
  5. Binary Tree: Maximum Depth of Binary Tree

演算法L1

  1. Binary Search
  2. Recursion
  3. Divide and Conquer
  4. Two Pointer
  5. Prefix Sum
  6. BFS/DFS（Binary Tree, Binary Search Tree）
  7. Greedy（練習時先寫 Easy 題就好）
  8. Bit Manipulation（練習時先寫 Easy 題就好）

推薦題目

  1. Binary Search: Binary Search
  2. Recursion:Fibonacci NumberInvert Binary Tree
  3. Two Pointer: Two Sum II — Input array is sorted
  4. Prefix Sum: Minimum Size Subarray Sum
  5. BFS / DFS:Binary Tree Level Order TraversalValidate Binary Search Tree
  6. Divide and Conquer: Sort an Array (練習寫 Merge Sort & Quick Sort)
  7. Greedy (Easy): Assign Cookies
  8. Bit Manipulation (Easy): Counting Bits

實戰應用L1

在練功坊學會招式之後，靈活運用才是重點，在這個區域的題目，通常背後隱藏的概念不會太難，但就是不容易一眼看穿，解法會比上面練功坊的題目藏的更深，或需要轉更多的彎。面對這種問題，我們要學會忘掉所有你學會的招式，返璞歸真回到最原始的狀態。簡言之，找回面對任何問題的初心，也就是

  1. 觀察規律
  2. 分類歸納不同情境
  3. 對每個情境一一處理

最後，記得挑選能力範圍內的題目去挑戰

  • 失敗的成長循環：隨便開一題 -> 想破頭不會做 -> 開解答看很久才看懂 -> 感到疲累 -> 沒動力再打開下一題暫時放棄 -> 很久以後又想到要練刷題 -> 隨便開一題
  • 成功的成長循環：挑選能力範圍內的題目 -> 慢慢分析歸納找到思路 -> 做出來獲得滿滿的成就感 -> 很想再開一題挑戰自我 -> 尋找適合的下一題繼續挑戰

如何找到動機

如果你長年都苦於找不到刷題動機，時不時燃起熱血想徹底搞定他，但沒多久又把這件事放一邊去，往復循環，我有另一篇專門寫如何找到動機來源的文章也可以看看。簡單筆記如下：

動機不能只是隨機的火花，你必須找到引燃自己的方式。而第一步就是不要讓你的動機永遠依賴於意志力，而是找到方法，只需開頭推動一下，後面就可以像滾雪球一樣源源不絕的產生動機，這才是長期成功之道。

  1. Leetcode 的特殊要求通常是以下幾個：
  2. Constant Extra Space：不使用任何額外記憶體，也就是 space complexity 要是 O(1)
  3. One Pass：不只時間複雜度要 O(N)，還只允許跑一輪迴圈
  4. In-place：直接對原始 input 做改變，不回傳答案，通常也隱含 Constant Extra Space 的條件
  5. Integer Limit：運算中任何一刻都不可以超過 Integer 範圍

四大動機產生方式

1. 營造好的環境

第一種動機來自外在環境，很容易，幫助也很大，但也來得快去得快，當你失去了環境，也就失去了動機。

  • 加入一個讀書會或團體課程，營造正向的學習環境。
  • 去圖書館念書，透過身旁人的狀態讓你產生動力。
  • 把你的目標昭告天下給朋友圈知道，請他們協助緊盯你的進度。
  • e.g. 通勤時間需要搭一小時的捷運，聽起來很累，但我買了一本電子書隨身帶著，每天的這來回兩小時就這樣變成了我的固定讀書時間，短短半年內消化了十來本好書（許多也成了這系列文的寶貴素材）

2. 透過連續完成小目標帶來的成就感

第二種遊戲式正循環的動機，可以持續比較久，對初期新手階段很有幫助，但當難度開始升高，很容易遇到瓶頸。

  1. 先選定合適難度的主題（例如 Two Pointer）去 Leetcode 或類似網站找一個適合自己程度的題目（從最簡單開始）
  2. 讀完題目後，先試著自己想想看（回想上一篇我們如何建立心智表徵）
  3. 如果超過 15 分鐘想不到，不要硬想，去討論區或網路上尋找教材或解答，但不要急著一次看完，可以看一點就好，一但有多出一點點靈感就退回步驟 3。
  4. 反覆 3 跟 4 循環，直到靠自己力量做出來（即使看了部分解答，只要最後有一小部分是靠自己想出來的也算），而每當我在努力掙扎一番後，看到下面這個綠勾勾跳出來，就是一個讓心情非常愉悅的獎勵。

當然若這個對你來說不夠，你也可以額外創造其他有效獎勵，在每次成功時發放。最終，一但我的大腦綁定了這個喜悅，他就會自動拉著我想要再挑戰下一題，然後再次努力，再次解決，再次獲得獎勵，不斷循環。如果你有了這樣的感受，恭喜你，你的正循環開關已經打開，讓他領著你前進一大段路吧！

自己挑題目最重要原則：寧可太簡單，不要太難，太簡單還可以緩步提升難度，太難有可能一下把自己的正循環打斷，拖延症就容易趁機發作而不想學習，得不償失。

3. 找到學習知識本身的喜悅

此時要開始找到第三種更純粹的內在動機，也就是學習本身帶來的樂趣，而且難度越高還會越有趣，若能以此做為你正循環真正動力核心來源，你就不需依靠任何外在的獎勵或回報，也能開心的一路往前走。

基因其實本來就決定了學習是快樂的！但為什麼很多人會有不快樂的學習經驗呢？
因為一但在有高度時間壓力的學習情況下，我們就變得很難快樂，因為同化跟順應都需要時間去消化，如果時間壓力太大，我們很難好好的走過這個流程，建立起越來越好的基模，並且從中獲得快樂，只會一直感受到不平衡的痛苦，然後東西也學不好。

4. 讓目標與你的長期人生使命一致

心流體驗往往發生在你面對的挑戰足夠高，而你同時也有足夠的技能完成，可能你正在進行一場把自己發揮到極致的運動競賽，或在學習過程中靠自己的力量完美解出了超級難題。此時的你會感到一種全心投入、身心合一、物我兩忘的狀態。

最後，假如能到達第四種動機 ，也就是心流的層次，還可以讓你的學習昇華到發自內心的至高喜悅，讓你願意一輩子永無止境的追尋下去。這也是一些偉大的數學家、物理學家、音樂家，如何從孩提時代的啟蒙，一路到願意犧牲奉獻一輩子在一個困難的題目或作品上，最終成就不朽。

特殊模式

Leetcode 的特殊要求通常是以下幾個：

  1. Constant Extra Space：不使用任何額外記憶體，也就是 space complexity 要是 O(1)
  2. One Pass：不只時間複雜度要 O(N)，還只允許跑一輪迴圈
  3. In-place：直接對原始 input 做改變，不回傳答案，通常也隱含 Constant Extra Space 的條件
  4. Integer Limit：運算中任何一刻都不可以超過 Integer 範圍

推薦題目

經典範例題目如下：

  1. Constant Extra Space: Single Number： Single Number 會需要一點 Bit Manipulation 的知識，稍微難一點。
  2. One Pass: Sort Colors：如果你以前 quick sort 有學好，其實就是 partition 做兩次而已，但加上 one pass 的條件後就不那麼容易了，要做出 3-way partition。
  3. In-place: Reverse String：相對簡單，只是要認識一下 in-place 的答題方式。
  4. Integer Limit: Divide Two Integers：考驗你對整數型別的範圍是否有足夠的敏感度，乍看之下是個超級簡單的問題，但如果細細思考，會發現有很多的麻煩在裡面，例如 input 的數值可能是 -2³¹，但假如你輕易的對他做絕對值運算，變成 2³¹ 就超出整數範圍了，算是不合格的做法。面對這種題目，假如你用 Python 或 Javascript 之類的語言，很可能會完全沒注意到這問題，因為他都內建大數運算。因此這類題目會建議用 JAVA 或 c/c++ 來做，且不能開 long 型別，要強迫自己熟悉 int 的特性。

挑戰模式

一些增加自我練習強度的方式，對任何題目、任何階段都適用，也就是除了單純完成題目得到 Accept 以外，你可以開始逐步增加對自己的要求，要求難度照以下為順序逐漸提高：

  1. 無論如何給出一個暴力解，通常你會看到 Time Limit Exceeded (TLE) 代表你的暴力解成功了，只是跑太慢所以比較大的測試資料沒辦法通過，否則會先看到 Wrong Answer (WA)，代表邏輯本身是錯的
  2. 從 Top 100 like 裡面隨機抽題，且不去看題目的分類，前面的訓練會讓人習慣已經知道分類的情況下解題，但真實面試的時候，你是不會有這個資訊的，得靠自己的觀察力找到答案
  3. Submit 後若沒通過時，不要看 Leetcode 給的測資，自己去發想測試資料來找到錯誤，這會磨練你思考 corner case 的能力，畢竟 on-site 面試或 phone interview 的時候，發想測資也是面試官很愛觀察的面向之一。
  4. 減少嘗試按 run 的測試次數，也減少在自己 IDE 上面測試的次數，更進一步可以要求自己完全不 run code，但一次 submit 就要通過，這會大幅增加挑戰的難度，因為你必須把邏輯想得非常透徹，確保沒有任何一絲漏洞，一般公司的面試不太會要求到這樣，但練習的時候可以視為一種負重訓練，考驗自己邏輯是否完全清晰，且養成寫 code 嚴謹紮實的好習慣。而最知名的 Google 面試，就是要求面試者要在類似 Google Doc 的工具上，在無法 run code 的情境下，自己想測資，並寫出真的能跑出正確結果且無 bug 的 code，是不是很刺激？

資料結構L2

從這裡開始，觀念的難度會上升一個層級，每個主題都可以想成一個遊戲中的小 boss，可能光看懂教學解說都需要費一番功夫，但這邊也是真正實力差距的開始，要想進 Top 公司，以下才是見證真功夫的時刻:
這區域中會出現一些較複雜的資料結構，或舊資料結構的進階應用，通常有以下這些主題，部分主題一樣可以看 Hackerearch 的介紹，或看我下面找到的連結。
這區域中會出現一些較複雜的資料結構，或舊資料結構的進階應用，通常有以下這些主題，部分主題一樣可以看 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

學習方法

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

推薦題目

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

  1. Monotonic Stack/Queue: Final Prices With a Special Discount in a Shop
  2. Tree:Insert into a Binary Search TreeConstruct 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 StackDesign Circular Queue
  7. Trie: Implement Trie (Prefix Tree)

演算法L2

如同上面的資料結構 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 StationNon-overlapping Intervals
  5. DP:Unique PathsCoin ChangeEdit Distance
  6. Bit Manipulation（Advanced）: Maximum XOR of Two Numbers in an Array

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

而其中最惡名昭彰的是 Dynamic Programming（DP），變化極為繁多，雖然都有一致的策略跟思考方向在，但每種新變化型都不容易在完全沒看過的狀況下憑空想出來，所以等於光他一個，就又可以拆成好幾個獨立的演算法來學了（常見的型大概就有 7, 8 種之多）。好消息是一般公司大概也不太敢去考太複雜的 DP 題目，頂多考經典型（太難的面試官都不一定會？），但如果目標是世界頂尖 Tier 1 公司，由於前面稍容易的問題競爭者們都會做，所以困難 DP 往往變成拿來最終鑑別實力的題，有志者不能輕易放棄。

實戰應用L2

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

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

學習方法

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

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

特殊模式

最後，還有一些在 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 也曾用過類似題目拍過實戰模擬面試的介紹影片，有興趣可以看我寫的這篇分析。