LeetCode 刷1500題心路歷程

15 min readDec 18, 2022

先附個圖，從2021/12/16買了一年premium開始從零開始刷到2022/12/16總共寫了1524題，並參加了58場weekly contest，基本上都以C++為主。

以下講了含初階到進階的內容，若你還是新手中的新手也不想看這麼多字，請直接從代碼隨想錄提供的200題包含講解開始刷起。

結論：時間充足的話請從代碼隨想錄200題開始刷

動機

起初只是為了準備FAANG等級的technical面試，到了後期目標轉向準備打各種年度競賽(e.g., Google Code Jam)，所以除了寫LeetCode，也有額外寫Codeforces的題以及打div2的比賽。此外，若LeetCode Contest Rating達到2300+，還有資格去應徵Internal Contest Tester (part time)。

什麼時候開始刷

越早越好，不要等到需要用到時(例如面試或打比賽)再開始，自己是碩士畢業後的一年利用工作閒暇之餘練習的，但這樣會挺勞累的。只是若還在學生時期，可能每天會很難有一段時間能好好練，需要有足夠的動機。

開始練習前的Prerequisite

至少先會任何語言的基本語法，並且修過資料結構及演算法。

要用什麼語言寫，以及對語言的熟悉程度

根據你所在地的各公司開出的職缺以及自己預計的發展目標選擇，若都沒想法C++是個不錯的選擇，因為職缺通常比較多，不過語言不是太大的問題，刷題只是練思維，想要轉換個語言只要記一下對應的資料結構用法即可，以及可能需要額外實作什麼資料結構。

例如使用C++刷題，沒意外的話會用到的standard template library (STL)只含vector、list、stack、queue、priority_queue、unordered_set、set、unordered_map、map、multiset、mulitmap需要額外實作的資料結構是Disjoint set、Trie、Binary index tree、Segment tree，若使用python，可能就沒有像C++有set (self-balancing binary search tree)能夠使用，需另求其他方法。

對於需要實作資料結構的狀況，建議練習到不需要思考就能憑著手感刻出來，例如實作Binary index tree時：

BIT {
private:
    vector<int> tree;
public:
    BIT(int n) {
        tree.resize(n + 1, 0);
    }
    
    int lsb(int x) {
        return x & (-x);
    }
    
    void add(int index, int value) {
        while (index < tree.size()) {
            tree[index] += value;
            index += lsb(index);
        }
    }
    int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= lsb(index);
        }   
        return sum;
    }
    int queryRange(int low, int high) {
        // [low, high]
        return query(high) - query(low - 1);
    }
};

盡量練習到不需要額外思考究竟要用 < 還是 ≤ ，或是lsb到底該怎麼做。

而對於一些常用演算法，如實作binary search時，很多人會遇到許多邊界狀況不太確定要用 < 還是 ≤的狀況，以下是個人最常用的模板：

int binarySearchLowerBound(vector<int>& v, int target) {
    int left = 0;
    int right = v.size();
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (v[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return left;
}

盡量練習到不需要額外思考究竟要用 < 還是 ≤ ，至於要用哪種模板，則看自己的喜好。另外因為使用C++，需要額外考慮overflow問題，才會有left + (right — left) / 2的這行，若是用python，就不用有這個疑慮，但除法則要記得得使用整數除法。

要不要買premium

如果只是想看解答，那非official的解答已經足夠了，也時常寫得比official更好，此外直接google search也能查到不錯的教學。但premium有附上各種不同類型題目的整理集，以及各大公司的tag，買一年來把能力練起來是挺划算的。

想找中文的解答以及講解

以下附一些可以參考的網站

[Youtube] Huifeng Guan：每週更新較困難的週賽題講解
[博客園] Grandyang：收錄題數很多，幾乎都找得到

最完整的題目分類

請參見這個repository(wisdompeak/LeetCode)，分類到非常細緻的境界

練習的順序

若時間急迫，那blind 75是個好的開始，若有一段時間可以練習，這邊提供自己寫題的順序

[0–100] blind 75
[100–300] 代碼隨想錄：非常好用，講解超詳細
[300–500] 花花酱 LeetCode 题目分類：開始寫一些難題
[500–700] Premium限定，Dynamic programing I, II, III, IV等套餐
[700–1000] Premium限定，依照各大公司的題目集，寫完(例如我把google題目集的全部400多題寫完了)
[1000–1500] 自由隨機練習，在這個階段我把題數#1~#950還沒寫的寫完，以及寫題時把遇到的相關題目也寫了，此時也有一陣子強迫自己只寫hard題

另外大約100題後能每天開始寫daily challenge，也能逐漸開始打weekly/biweekly contest。

要寫多少才夠

不少人會有疑惑究竟多少題才足夠面試，在這邊提供一點心境上的變化

[0–100] medium以上都非常卡，不會寫的題看解答都要好久
[100–300] 部分medium題目能自己完成了，也漸漸學到各種技巧
[300–500] 逐漸熟悉常見的套路題
[500–1000] contest有機會四題完賽
[1000–1500] contest幾乎都能四題完賽，此時練的是思維上通靈的速度以提升排名

所以基本上300題後非外商面試都不會有太大問題，500題後外商會有機會，不過真正判斷標準應該是以contest rating較客觀，也建議把1900+作為一個最低標：

1800+~1900+：非外商面試都不會有太大問題
1900+~2000+：Google外的外商面試都不會有太大問題
2100+~2200+：外商面試都不會有太大問題，除非不考你一般演算法題

另外若以題目難度來分，則：

1800+~1900+：medium能寫出來
1900+~2000+：medium能快速寫出來，hard可能有一半機率能寫出來
2100+~2200+：hard大部分都能寫出來

整理寫題的紀錄

為了能加速練習的進程，額外維護了一個google sheet來協助自己釐清不熟的題目，並且把寫過的題都分門別類整理在GitHub上。

google sheet上我標示了各種類別，另外也記錄了每次完成的日期，後期則在日期上額外加了顏色以區別當次完成的狀況，例如：

綠色：不看hint自己寫完並且時間/空間複雜度達到最佳
黃色：時間/空間複雜度尚待改進
橘色：看了hint
淺藍色：implementation有需要改進之處
紫色：看了解答但沒看實作
紅色：看了解答又看了實作

這樣每當下次daily challenge遇到之前已經綠色的題目，則可直接跳過避免浪費時間。

空間時間複雜度(time/space complexity)需要追求到什麼極致

很多人非常在意究竟能不能在time/space complexity上beat 100%，但基本上只要確定在big-O範疇跟最佳解一樣即可，例如一題array題，最佳解time complexity是O(N)，但自己只想到O(N²)或O(NlogN)的算法，那就需要額外學一下O(N)怎麼辦到的。

而許多的linked list題，常常有把O(2N)降到O(N)即single pass的技巧，若有時間這部分也是直得參考的，惝若你已經實作了一個O(N)算法且你確信自己的implementation前面的常數很小卻有沒辦法beat 100%，那去參考別人怎麼達到beat 100%就不是優先事項。舉#876 Middle of the Linked List為例，題目是要取出linked list最中間node的值：

最簡單的做法可能是把linked list的值倒出來到一個vector<int>裡，此時就能得到size並直接從vector拿出最中間的點的值，這個方法time complexity是O(2N)，space complexity是O(N)
接著思考能不能不要把值取出的方法，若跑過兩次linked list，第一次得知node有多少個，第二次跑到中間時直接拿取答案，這樣這個方法time complexity是O(2N)，space complexity是O(1)
而最佳方法則是用slow/fast pointer，如以下所示time complexity是O(N)，space complexity是O(1)，其中這題不用使用sentinel技巧，只是個人習慣操作linked list題會加上sentinel。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* sentinel = new ListNode(0, head);
        ListNode* slow = sentinel;
        ListNode* fast = sentinel;
        while(fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow->next;
    }
};

另外dynamic program題也有許多降space complexity的技巧，例如把space complexity O(N²)降到O(N)，或把O(N)降到O(1)。這也是有閒暇時值得學的。

有一題經典的#300. Longest Increasing Subsequence，就有很多不同複雜度的寫法：

Brute-force: time complexity O(2^N); space complexity O(N)
Dynamic program: time complexity O(N²); space complexity O(N)
Binary search/BIT/Segment Tree: time complexity O(NlogN); space complexity O(N)

這題的進階題#2407. Longest Increasing Subsequence II則是必須使用Maximum Segment Tree才能達到不超時的時間複雜度。

通靈出時間複雜度的需求

比賽或寫題時，除了以自身經驗判斷最低的複雜度外，也能透過題目測資來猜測，例如：

N=10⁵以上：time complexity只能接受O(N)或O(NlogN)
N=10³~10⁴：time complexity可接受O(N²)
N=10²：time complexity可接受O(N³)
N=神秘數字(不一定)，此時要猜測是否轉化題目而降低複雜度，例如#2272 Substring With Largest Variance可以從iterate string變成iterate char (a->z)來降低複雜度

舉一個例子驗證多寫題目對思維的幫助

這邊以2022/12/11週賽#2503. Maximum Number of Points From Grid Queries舉例，驗證多寫題目在思維上的助益。

這題給了一個矩陣(m x n)，再給了一個query array Q長度為k，要回傳一個長度為k的array A，裡面每個數值A[i]是假設當下Q[i]為最高限制，那從matrix左上角開始走，可以走上下左右，遇到比Q[i]則不走，那可以走多少個cell。

這題如果直接brute force解，對於每個query開始從矩陣左上角BFS，複雜度為O(mnk)，不可接受。

這題比賽當下看完題目我就想到了解法，所以時間就僅花在implementation上：

重新排序query，從小到大，並且記錄原先數值在query中的index：在許多medium~hard題有用這個技巧(待我翻找出來後更新)。
因為query變成由小到大，那對應的answer也會從小到大，所以對於每個Q[i]，只要目前所在的點周圍比該數值低，就繼續走，也就是隨著query增加，逐漸拓增版圖：在許多medium~hard題有用這個技巧(待我翻找出來後更新)。

解題的思維或技巧，需要在很多練習下建立起自己的資料庫，每遇到新的題目就拿來用用看。

統整一些題目類型（粗體者是一定要精熟的）

Simulation：題目說什麼就照著做，通常測資很小就沒問題
String：非常多元，實質上是array，這種題目在hard上可能可以以char的iteration來考慮，要細分的話尚有Rabin-Karp與KMP兩個類型
Array：千奇百怪，細分則還有Prefix sum與Difference array類型
Matrix：千奇百怪，細分同上還有Prefix sum與Difference array類型
Linked list：挺單一的
Stack：挺單一的，但萬一出了Monotonic stack就很需要解題技術
Queue：挺單一的
Deque：挺單一的，但萬一出了Monotonic deque就很需要解題技術
Two pointers(=sliding window)：常用的技巧
Backtracking：常用的技巧，本質算是DFS
BFS/DFS：常用
Disjoint set (=Union find)：常常可以神奇地解掉問題
Greedy：常用的技巧，DP的每次狀態轉移也算是一種greedy
Tree：千奇百怪，使用DFS recursive方式能解掉許多困難題
Quad Tree：不常見
Self-balanced binary search tree/Multiset：常用的結構拿來解如729. My Calendar I, 731. My Calendar II, 732. My Calendar III類似的題
Trie：常常一看就知道要用它
Binary Index Tree (Fenwick tree)：偏不常見
Segment tree：不常見
Heap(=Priority queue)：會時常在greedy算法中使用
Graph：主要含Topological sort、Dijkstra’s algorithm、Bellman-Ford algorithm、Tarjan’s algorithm、Hierholzer’s algorithm，出現率由大到小
Binary search：很重要，拿來搜答案，LeetCode中有一篇技巧文值得一讀
Dynamic programming：千奇百怪
Divide and conquer：不常見
Bit operation：千奇百怪，在DP中使用的bit mask可能也算這類型的應用
Geometry：千奇百怪，像是Andrew’s Monotone Chain
System design：須結合上面各種結構技巧
Math：考驗數學知識水平與通靈能力，如Bézout’s identity、Algorithm R、Qubit
Others：De Bruijn sequence with Eulerian Circuit、Boyer-Moore Voting Algorithm、Kadane’s algorithm(屬於greedy的一種)、Sieve of Eratosthenes、Binary lifting

總結

一開始會是非常艱難的過程，但真的花時間練下去，進步是很可觀的，例如在多年前課堂作業出了#723. Candy Crush (當時並沒特別去網路上找答案就自己開刻了)，花了將近20小時才完成，如今，只要10分鐘就能完成了！另外這些演算法思維，只要維持著，那在工作或面試等都時不時有相當助益，也能避免突然需要用上時沒空練習的窘境。

若對寫題目還有其他問題或是想進行google style mock interview，歡迎來信詢問(ikaminyou@gmail.com)。