你面試穩了!通關LeetCode刷題完整攻略,省時又高效

最近拿到了Google的實習offer，來給大家增強信心。加油！

先照著這個分類來一波吧，保證有奇效！

按照分類刷，每個分類的題目，解法類似，這樣就用一個思路解一類題目了：

方便大家閱讀，我把內容也貼出來放在這個回答下：

1. Pattern: Sliding window，滑動窗口類型

滑動窗口類型的題目經常是用來執行數組或是鍊表上某個區間（窗口）上的操作。比如找最長的全為1的子數組長度。滑動窗口一般從第一個元素開始，一直往右邊一個一個元素挪動。當然了，根據題目要求，我們可能有固定窗口大小的情況，也有窗口的大小變化的情況。

該圖中，我們的窗子不斷往右一格一個移動

下面是一些我們用來判斷我們可能需要上滑動窗口策略的方法：

這個問題的輸入是一些線性結構：比如鍊表呀，數組啊，字符串啊之類的

經典題目：

Maximum Sum Subarray of Size K (easy)

Smallest Subarray with a given sum (easy)

Longest Substring with K Distinct Characters (medium)

Fruits into Baskets (medium)

No-repeat Substring (hard)

Longest Substring with Same Letters after Replacement (hard)

Longest Subarray with Ones after Replacement (hard)

2. Pattern: two points, 雙指針類型

雙指針是這樣的模式：兩個指針朝著左右方向移動（雙指針分為同向雙指針和異向雙指針），直到他們有一個或是兩個都滿足某種條件。雙指針通常用在排好序的數組或是鍊表中尋找對子。比如，你需要去比較數組中每個元素和其他元素的關係時，你就需要用到雙指針了。

我們需要雙指針的原因是：如果你只用一個指針的話，你得來回跑才能在數組中找到你需要的答案。這一個指針來來回回的過程就很耗時和浪費空間了 — 這是考慮算法的複雜度分析的時候的重要概念。雖然brute force一個指針的解法可能會奏效，但時間複雜度一般會是O(n²)。在很多情況下，雙指針能幫助我們找到空間或是時間複雜度更低的解。

上圖是說，我們在排好序的數組裡面找是否有一對數加起來剛好等於目標和

識別使用雙指針的招數：

一般來說，數組或是鍊表是排好序的，你得在裡頭找一些組合滿足某種限制條件

經典題目：

Pair with Target Sum (easy)

Remove Duplicates (easy)

Squaring a Sorted Array (easy)

Triplet Sum to Zero (medium)

Triplet Sum Close to Target (medium)

Triplets with Smaller Sum (medium)

Subarrays with Product Less than a Target (medium)

Dutch National Flag Problem (medium)

3. Pattern: Fast & Slow pointers, 快慢指針類型

這種模式，有一個非常出門的名字，叫龜兔賽跑。 咱們肯定都知道龜兔賽跑啦。但還是再解釋一下快慢指針：這種算法的兩個指針的在數組上（或是鍊表上，序列上）的移動速度不一樣。還別說，這種方法在解決有環的鍊表和數組時特別有用。

通過控制指針不同的移動速度（比如在環形鍊表上），這種算法證明了他們肯定會相遇的。快的一個指針肯定會追上慢的一個（可以想像成跑道上面跑得快的人套圈跑得慢的人）。

上面這個圖演示了快慢兩個指針最終在5相遇了

咋知道需要用快慢指針模式勒？

那啥時候用快慢指針而不是上面的雙指針呢？

有些情形下，咱們不應該用雙指針，比如我們在單鍊表上不能往回移動的時候。一個典型的需要用到快慢指針的模式的是當你需要去判斷一個鍊表是否是回文的時候。

經典題目：

LinkedList Cycle (easy)

Start of LinkedList Cycle (medium)

Happy Number (medium)

Middle of the LinkedList (easy)

4. Pattern: Merge Intervals，區間合併類型

區間合併模式是一個用來處理有區間重疊的很高效的技術。在設計到區間的很多問題中，通常咱們需要要麼判斷是否有重疊，要麼合併區間，如果他們重疊的話。這個模式是這麼起作用的：

給兩個區間，一個是a，另外一個是b。別小看就兩個區間，他們之間的關係能跑出來6種情況。詳細的就看圖啦。

理解和識別這六種情況，灰常重要。因為這能幫你解決一大堆問題。這些問題從插入區間到優化區間合併都有。

怎麼識別啥時候用合併區間模式呀？

經典題目：

Merge Intervals (medium)

Insert Interval (medium)

Intervals Intersection (medium)

Conflicting Appointments (medium)

5. Pattern: Cyclic Sort，循環排序

這種模式講述的是一直很好玩的方法：可以用來處理數組中的數值限定在一定的區間的問題。這種模式一個個遍歷數組中的元素，如果當前這個數它不在其應該在的位置的話，咱們就把它和它應該在的那個位置上的數交換一下。你可以嘗試將該數放到其正確的位置上，但這複雜度就會是O(n^2)。這樣的話，可能就不是最優解了。因此循環排序的優勢就體現出來了。

咋鑑別這種模式？

這些問題一般設計到排序好的數組，而且數值一般滿足於一定的區間如果問題讓你需要在排好序/翻轉過的數組中，尋找丟失的/重複的/最小的元素

經典題目：

Cyclic Sort (easy)

Find the Missing Number (easy)

Find all Missing Numbers (easy)

Find the Duplicate Number (easy)

Find all Duplicate Numbers (easy)

6. Pattern: In-place Reversal of a LinkedList，鍊表翻轉

在眾多問題中，題目可能需要你去翻轉鍊表中某一段的節點。通常，要求都是你得原地翻轉，就是重複使用這些已經建好的節點，而不使用額外的空間。這個時候，原地翻轉模式就要發揮威力了。

這種模式每次就翻轉一個節點。一般需要用到多個變量，一個變量指向頭結點（下圖中的current），另外一個（previous）則指向咱們剛剛處理完的那個節點。在這種固定步長的方式下，你需要先將當前節點（current）指向前一個節點（previous），再移動到下一個。同時，你需要將previous總是更新到你剛剛新鮮處理完的節點，以保證正確性。

咱們怎麼去甄別這種模式呢？

如果你被問到需要去翻轉鍊表，要求不能使用額外空間的時候

經典題目：

Reverse a LinkedList (easy)

Reverse a Sub-list (medium)

Reverse every K-element Sub-list (medium)

7. Pattern: Tree Breadth First Search，樹上的BFS

這種模式基於寬搜（Breadth First Search (BFS)），適用於需要遍歷一顆樹。藉助於隊列數據結構，從而能保證樹的節點按照他們的層數列印出來。列印完當前層所有元素，才能執行到下一層。所有這種需要遍歷樹且需要一層一層遍歷的問題，都能用這種模式高效解決。

這種樹上的BFS模式是通過把根節點加到隊列中，然後不斷遍歷直到隊列為空。每一次循環中，我們都會把隊頭結點拿出來（remove），然後對其進行必要的操作。在刪除每個節點的同時，其孩子節點，都會被加到隊列中。

識別樹上的BFS模式：

如果你被問到去遍歷樹，需要按層操作的方式（也稱作層序遍歷）

經典題目：

Binary Tree Level Order Traversal (easy)

Reverse Level Order Traversal (easy)

Zigzag Traversal (medium)

Level Averages in a Binary Tree (easy)

Minimum Depth of a Binary Tree (easy)

Level Order Successor (easy)

Connect Level Order Siblings (medium)

8. Pattern: Tree Depth First Search，樹上的DFS

樹形DFS基於深搜（Depth First Search (DFS)）技術來實現樹的遍歷。

咱們可以用遞歸（或是顯示棧，如果你想用迭代方式的話）來記錄遍歷過程中訪問過的父節點。

該模式的運行方式是從根節點開始，如果該節點不是葉子節點，我們需要幹三件事：

需要區別我們是先處理根節點（pre-order，前序），處理孩子節點之間處理根節點（in-order，中序），還是處理完所有孩子再處理根節點（post-order，後序）。

識別樹形DFS：

經典題目：

Binary Tree Path Sum (easy)

All Paths for a Sum (medium)

Sum of Path Numbers (medium)

Path With Given Sequence (medium)

Count Paths for a Sum (medium)

9. Pattern: Two Heaps，雙堆類型

很多問題中，我們被告知，我們拿到一大把可以分成兩隊的數字。為了解決這個問題，我們感興趣的是，怎麼把數字分成兩半？使得：小的數字都放在一起，大的放在另外一半。雙堆模式就能高效解決此類問題。

正如名字所示，該模式用到了兩個堆，是不是很難猜？一個最小堆用來找最小元素；一個最大堆，拿到最大元素。這種模式將一半的元素放在最大堆中，這樣你可以從這一堆中秒找到最大元素。同理，把剩下一半丟到最小堆中，O(1)時間找到他們中的最小元素。通過這樣的方式，這一大堆元素的中位數就可以從兩個堆的堆頂拿到數字，從而計算出來。

判斷雙堆模式的秘訣：

這種模式在優先隊列，計劃安排問題（Scheduling）中有奇效有時候，這種模式在涉及到二叉樹數據結構時也特別有用

經典題目：

Find the Median of a Number Stream (medium)

Sliding Window Median (hard)

Maximize Capital (hard)

10. Pattern: Subsets，子集類型，一般都是使用多重DFS

超級多的編程面試問題都會涉及到排列和組合問題。子集問題模式講的是用BFS來處理這些問題。

這個模式是這樣的：

給一組數字 [1, 5, 3]

把第一個數（1），加到之前已經存在的集合中：[[], [1]];把第二個數（5），加到之前的集合中得到：[[], [1], [5], [1,5]];再加第三個數（3），則有：[[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]].

該模式的詳細步驟如下：

如果判斷這種子集模式：

經典題目：

Subsets (easy)

Subsets With Duplicates (easy)

Permutations (medium)

String Permutations by changing case (medium)

Balanced Parentheses (hard)

Unique Generalized Abbreviations (hard)

11. Pattern: Modified Binary Search，改造過的二分

當你需要解決的問題的輸入是排好序的數組，鍊表，或是排好序的矩陣，要求咱們尋找某些特定元素。這個時候的不二選擇就是二分搜索。這種模式是一種超級牛的用二分來解決問題的方式。

對於一組滿足上升排列的數集來說，這種模式的步驟是這樣的：

首先，算出左右端點的中點。最簡單的方式是這樣的：middle = (start + end) / 2。但這種計算方式有不小的概率會出現整數越界。因此一般都推薦另外這種寫法：middle = start + (end — start) / 2

如果要找的目標改好和中點所在的數值相等，我們返回中點的下標就行

如果目標比中點在的值小（key < arr[middle]）：將下一步搜索空間放到左邊（end = middle - 1）如果比中點的值大，則繼續在右邊搜索，丟棄左邊：left = middle + 1

圖示該過程的話，如下圖所示：

經典題目：

Order-agnostic Binary Search (easy)

Ceiling of a Number (medium)

Next Letter (medium)

Number Range (medium)

Search in a Sorted Infinite Array (medium)

Minimum Difference Element (medium)

Bitonic Array Maximum (easy)

12. Pattern: Top 『K』 Elements，前K個系列

任何讓我們求解最大/最小/最頻繁的K個元素的題，都遵循這種模式。

用來記錄這種前K類型的最佳數據結構就是堆了（譯者註：在Java中，改了個名，叫優先隊列（PriorityQueue））。這種模式藉助堆來解決很多這種前K個數值的問題。

這個模式是這樣的：

遍歷剩下的還沒訪問的元素，如果當前出來到的這個元素比堆頂元素大，那咱們把堆頂元素先刪除，再加當前元素進去。

注意這種模式下，咱們不需要去排序數組，因為堆具有這種良好的局部有序性，這對咱們需要解決問題就夠了。

識別最大K個元素模式：

經典題目：

Top 『K』 Numbers (easy)

Kth Smallest Number (easy)

『K』 Closest Points to the Origin (easy)

Connect Ropes (easy)

Top 『K』 Frequent Numbers (medium)

Frequency Sort (medium)

Kth Largest Number in a Stream (medium)

『K』 Closest Numbers (medium)

Maximum Distinct Elements (medium)

Sum of Elements (medium)

Rearrange String (hard)

13. Pattern: K-way merge，多路歸併

K路歸併能幫咱們解決那些涉及到多組排好序的數組的問題。

每當你的輸入是K個排好序的數組，你就可以用堆來高效順序遍歷其中所有數組的所有元素。你可以將每個數組中最小的一個元素加入到最小堆中，從而得到全局最小值。當我們拿到這個全局最小值之後，再從該元素所在的數組裡取出其後面緊挨著的元素，加入堆。如此往復直到處理完所有的元素。

該模式是這樣的運行的：

取出堆頂元素（全局最小），將該元素放入排好序的結果集合裡面

識別K路歸併：

如果問題讓咱們合併多個排好序的集合，或是需要找這些集合中最小的元素

經典題目：

Merge K Sorted Lists (medium)

Kth Smallest Number in M Sorted Lists (Medium)

Kth Smallest Number in a Sorted Matrix (Hard)

Smallest Number Range (Hard)

14. Pattern: 0/1 Knapsack (Dynamic Programming)，0/1背包類型

經典題目：

0/1 Knapsack (medium)

Equal Subset Sum Partition (medium)

Subset Sum (medium)

Minimum Subset Sum Difference (hard)

15. Pattern: Topological Sort (Graph)，拓撲排序類型

拓撲排序模式用來尋找一種線性的順序，這些元素之間具有依懶性。比如，如果事件B依賴於事件A，那A在拓撲排序順序中排在B的前面。

這種模式定義了一種簡單方式來理解拓撲排序這種技術。

這種模式是這樣奏效的：

初始化
a) 藉助於HashMap將圖保存成鄰接表形式。
b) 找到所有的起點，用HashMap來幫助記錄每個節點的入度創建圖，找到每個節點的入度
a) 利用輸入，把圖建好，然後遍歷一下圖，將入度信息記錄在HashMap中找所有的起點
a) 所有入度為0的節點，都是有效的起點，而且我們講他們都加入到一個隊列中排序
a) 對每個起點，執行以下步驟
—i) 把它加到結果的順序中
— ii)將其在圖中的孩子節點取到
— iii)將其孩子的入度減少1
— iv)如果孩子的入度變為0，則改孩子節點成為起點，將其加入隊列中
b) 重複（a）過程，直到起點隊列為空。

拓撲排序模式識別：

經典題目：

Topological Sort (medium)

Tasks Scheduling (medium)

Tasks Scheduling Order (medium)

All Tasks Scheduling Orders (hard)

Alien Dictionary (hard)

大家好好練練這些題目，面試中遇到中高等難度的題目，應該就能解得不錯了。

第二門則是單獨將動態規劃（DP）的題目進行了細分。

提到算法，繞不開的重點和難點就肯定會包括動態規劃 -- DP，本文就把經典的DP問題按照分類列一下，大家可以按照Recursion，Top-Down，Bottom-Up三種方式都練一練。俗話說，熟能生巧，多練才是提高算法的不二法寶。

課程詳細的內容，可以參考這裡：

Grokking Dynamic Programming Patterns for Coding Interviews[1]

該門課程中, 作者將DP的問題分成以下幾類:

1. 0/1 Knapsack, 0/1背包，6個題

0/1 Knapsack，0/1背包問題

Equal Subset Sum Partition，相等子集劃分問題

Subset Sum，子集和問題

Minimum Subset Sum Difference，子集和的最小差問題

Count of Subset Sum，相等子集和的個數問題

Target Sum，尋找目標和的問題

2. Unbounded Knapsack，無限背包，5個題

Unbounded Knapsack，無限背包

Rod Cutting，切鋼條問題

Coin Change，換硬幣問題

Minimum Coin Change，湊齊每個數需要的最少硬幣問題

Maximum Ribbon Cut，絲帶的最大值切法

3. Fibonacci Numbers，斐波那契數列，6個題

Fibonacci numbers，斐波那契數列問題

Staircase，爬樓梯問題

Number factors，分解因子問題

Minimum jumps to reach the end，蛙跳最小步數問題

Minimum jumps with fee，蛙跳帶有代價的問題

House thief，偷房子問題

4. Palindromic Subsequence，回文子系列，5個題

Longest Palindromic Subsequence，最長回文子序列

Longest Palindromic Substring，最長回文子字符串

Count of Palindromic Substrings，最長子字符串的個數問題

Minimum Deletions in a String to make it a Palindrome，怎麼刪掉最少字符構成回文

Palindromic Partitioning，怎麼分配字符，形成回文

5. Longest Common Substring，最長子字符串系列，13個題

Longest Common Substring，最長相同子串

Longest Common Subsequence，最長相同子序列

Minimum Deletions & Insertions to Transform a String into another，字符串變換

Longest Increasing Subsequence，最長上升子序列

Maximum Sum Increasing Subsequence，最長上升子序列和

Shortest Common Super-sequence，最短超級子序列

Minimum Deletions to Make a Sequence Sorted，最少刪除變換出子序列

Longest Repeating Subsequence，最長重複子序列

Subsequence Pattern Matching，子序列匹配

Longest Bitonic Subsequence，最長字節子序列

Longest Alternating Subsequence，最長交差變換子序列

Edit Distance，編輯距離

Strings Interleaving，交織字符串

大家可以先把以上35個題目練熟，這樣DP到達中等水平肯定是okay了的。再加以訓練和提高。突破算法的硬骨頭不在話下。一定要按照三種方式對照起來練。

DP課程題目合集的傳送門：

窮碼農：動態規劃及面試，學完這一篇，你就入門了：Dynamic Programming, 動態規劃，經典題目[2]

以上。

更新一下國外LeetCode大神們是怎麼刷LeetCode的：

窮碼農：LeetCode到底應該怎麼刷？面試應該注意哪些問題？大公司到底怎麼進？來看看LC大神們的刷題攻略！[3]

另外一個回答的傳送門：

刷完LeetCode是什麼水平，能拿到什麼水平的 offer ？[4]

LeetCode 2019美版官方精華經驗合集在這裡：

https://leetcode.com/discuss/general-discussion/459286/Year-in-Review\%3A-2019[5]

參考資料

[1]Grokking Dynamic Programming Patterns for Coding Interviews: https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews?aff=K7qB

[2]窮碼農：動態規劃及面試，學完這一篇，你就入門了：Dynamic Programming, 動態規劃，經典題目: https://zhuanlan.zhihu.com/p/89391817

[3]窮碼農：LeetCode到底應該怎麼刷？面試應該注意哪些問題？大公司到底怎麼進？來看看LC大神們的刷題攻略！: https://zhuanlan.zhihu.com/p/98580817

[4]刷完LeetCode是什麼水平，能拿到什麼水平的 offer ？: https://www.zhihu.com/question/32019460/answer/875114975

[5]https://leetcode.com/discuss/general-discussion/459286/Year-in-Review%3A-2019: https://link.zhihu.com/?target=https%3A//leetcode.com/discuss/general-discussion/459286/Year-in-Review%253A-2019

[6]窮碼農：別再埋頭刷LeetCode之：北美算法面試的題目分類，按類型和規律刷題，事半功倍: https://zhuanlan.zhihu.com/p/89392459

[7]Grokking the Coding Interview: Patterns for Coding Questions: https://www.educative.io/courses/grokking-the-coding-interview?aff=K7qB