良好風格的 LeetCode 解決方案

This document provides a comprehensive overview of LeetCode-Solutions-in-Good-Style, a resource offering beginner-friendly tutorials and video solutions for algorithm and data structure problems. It features a structured building a strong understanding of fundamental concepts rather than competitive coding.

LeetCode-Solutions-in-Good-Style

說明：我和絕大多數同學一樣，一邊學習、一邊總結。我會爭取做更多的分享，帶給大家一些有用的知識，感謝大家一直以來的支持。

大家好，這裡是一個《演算法與資料結構》的入門級教程，適用於演算法零基礎和轉行同學，不適合準備演算法競賽。想傳遞的觀點是：寫邏輯清楚的程式碼，所以我寫的程式碼一定經過了嚴格的思考，格式非常標準，不帶有個人風格，不會為了縮減程式碼行數而少寫一個空行和註解。在這裡：

可以叫我weiwei，在我力所能及且時間允許的情況下，我會盡可能回答我知道的問題。如果有無法及時回覆的問題，可能是因為我沒有看到站內通知，可以寄email給我[email protected] 。

我錄製的影片題解

我從2019 年9 月開始錄製影片題解。最開始的時候，我會對著要說的資料錄好幾遍。現在講解知識點的時候寫逐字稿。已經沉澱了很多視頻，其實也算是一個小小的體系課程，現在羅列在這裡，希望能夠對大家有所幫助。

0. 演算法新手如何刷力扣（LeetCode）？ 【乾貨分享】

1. 時間複雜度與空間複雜度

這個影片提到了時間複雜度是一個漸進概念，需要用動態的角度去理解。並且講解了時間複雜度的嚴格定義（極限形式），以便大家理解時間複雜度的計算規則。並且還指出了：時間複雜度不是程式的運行時間；應該使用「空間換時間」，而更著重於優化「時間複雜度」。

2. 二分查找

這個影片介紹如何寫對二分查找演算法，二分查找的細節雖然多，但只要我們掌握了正確的解題思路，並且多加練習、勤於思考、多做總結，寫對二分查找的問題就不再困難。

下面的影片講解了幾道二分查找的例題，我們重點分析了題意和如何利用題目中給出的條件逐漸縮小搜尋區間。

我們透過「力扣」第4 題（找出兩個正序數組的中位數）的分析，向大家介紹了這樣的技巧：如果要找的目標元素的性質比較複雜，可以對這性質取反，進而寫出可以簡單的可以縮減問題區間的邏輯語句。

3. 和排序相關的問題

「歸併排序」和「快速排序」是非常重要的排序演算法，深刻理解它們對於理解「遞歸」函數的運行機制有著非常大的幫助，同時它們也是「分治思想」的典型應用。 「逆序對」和「荷蘭國旗問題（顏色分類）」也是非常經典的演算法問題。

計算「逆序對」完全就是依照「歸併排序」的思路而來。

在「顏色分類」問題的講解中，我們向大家介紹了「循環不變量」，在編寫程式碼的過程中，我們應該一直遵守所使用的變數的語義，在「程式執行前」「執行過程中」 「執行結束」日後維持不變。遵守我們自己定義「循環不變量」是我們寫對正確程式碼的重要方法。

「缺失的第一個正數」是一個經典的演算法問題，用到的想法是「原地哈希」，可以理解為是「桶排序」演算法的特殊應用：一個蘿蔔一個坑，一個桶裡只存放一個元素。要和大家強調的是，可以這樣做是和輸入數組的元素的數值密切相關。

4. 滑動視窗

「滑動視窗」問題是典型的應用「循環不變量」解決的問題，比較考驗我們編碼和調試的能力。

5. 堆疊相關的問題

使用「堆疊」解決的問題，需要我們透過具體例子，發現解決它們正好符合「後進先出」的規律：

掌握下面這兩個問題，離不開對具體例子的研究，進而歸納出一般規律。

「棧」最廣泛的一種應用就是作為「遞歸」「深度優先遍歷」「分治演算法」的資料結構支援。

6. 並查集

「並查集」這個資料結構目前來說在面試中出現比較少，如果是準備演算法面試的朋友，可以跳過。

7. 樹

樹的問題很多都可以用「深度優先遍歷」或「廣度優先遍歷」去做。

8. 回溯演算法

「回溯演算法」其實就是對題目中所蘊含的「樹狀結構」執行一次深度優先遍歷。做這一類問題，在草稿紙上畫出樹狀結構圖很重要。

9. 動態規劃

10. 廣度優先遍歷與拓樸排序

11. 哈希表

12. 位元運算相關

我的個人網站和演算法學習筆記

微信群與QQ 群

如果需要一起刷題的朋友，可以加入微信群組和QQ 群組。

我的LeetBook

這裡為自己做一個宣傳，我最近在「力扣」上推出了自己的LeetBook：零起步學演算法（原名《使用「力扣」學習演算法與資料結構》），主要面向轉行、零基礎的朋友，講解演算法與資料結構的基礎知識。

說明：

這張LeetBook 的前兩章（ 時間複雜度、二分查找）是免費閱讀的，後面的章節需要付費閱讀，非會員價99 元，會員價69 元，您目前看到的主頁目錄與LeetBook 是一樣的，只有多出來的部分，不會更少；

LeetBook 的課程標題、範例、練習、配套程式碼倉庫（就是您目前看到的這個倉庫）是完全公開的，如果LeetBook 裡設計的內容（包括練習）您已經掌握，就不太建議購買；

投入精力與平時寫題解是一樣的，只不過LeetBook 在製作圖表上會更細緻一點。付費內容是：製作教學的時間精力付出、「力扣」的工作人員和高手參與製作和審核，閱讀體驗會更好。不排除平時寫的題解知識點比LeetBook 還要多；

中、高階用戶請謹慎購買；

可以在「力扣」站內或我的其他社交帳號向我諮詢課程內容，也可以向本倉庫提issue。不管是否購買課程，我都會盡量回答我所知道的問題（時間允許，能力範圍之內）。感謝大家一直以來，一如既往對我的支持。有建議和意見也歡迎大家與我交流；

我所講解的知識在我曾經向大家推薦的書籍，我寫的博客、題解和筆記裡都有，已經發布的題解、博客、筆記都會一直共享，並且只要我有時間和精力，我還會堅持做分享和答疑；

很感謝「力扣」給我機會做課程的機會，幫助我完成一個小心願。

「力扣」分類以及題解目錄（依照LeetBook 的章節編排，第16 章以後為目前LeetBook 不包含的章節）

說明：題目分類與我的LeetBook 章節對應。

第1 章時間複雜度

這部分內容介紹了時間複雜度這個概念，可以收看【影片講解】 ，完全免費。 這章節沒有練習。

第2 章二分查找

題型一：二分求下標

說明：

練習：

題型二：二分確定一個有範圍的整數（二分答案）

算法思想：減而治之。如果題目要我們找一個整數，這個整數有確定的範圍，可以透過二分查找逐漸縮小範圍，最後逼近到一個數。

題型三：複雜的判別函數（最大值極小化問題）

說明：這一類問題本質上還是「題型二」（二分答案），但是初學的時候會覺得有些繞。這一類問題的問法都差不多，關鍵字是「連續」、「正整數」，請大家注意捕捉題目中這樣的關鍵訊息。

第3 章基礎排序演算法

這一部分包含了四種基礎排序演算法：選擇排序、插入排序、希爾排序、冒泡排序。

「力扣」第912 題：排序數組的題解：總結了排序問題的一些要點和學習資料，可以從排序問題開始學習演算法。

數組的問題可以作為演算法“新手場”，因為這些問題只需要掌握程式語言的基礎知識就可以完成。以下問題都很容易想到解決方案，即使沒有學習過相關的資料結構和演算法知識。

知識點：循環不變量

第4 章高階排序演算法（重要）

這一部分需要重點掌握三種高階排序演算法：歸併排序、快速排序、堆排序。

說明：

第5 章非比較排序（選學）

這一部分包含了三種非比較排序排序：計數排序、基數排序、桶排序。解決這些問題需要知道原地哈希這個概念。

第6 章滑動視窗與雙指針

一、滑動窗口

滑動視窗的參考寫法（不是模板，請不要原樣照搬，僅供參考，理解演算法設計想法是更重要的）：

友情提示：第3 題和第76 題是必須會做的基本問題。上面的問題理解透徹了，下面的問題就可以比較輕鬆地做出來。

重點問題：

說明：

練習：

說明：

第209 題：題目中給出的關鍵訊息：數組裡的元素全部都是正整數。共有以下3 種方法。

方法一：暴力解法

方法二：滑動視窗（分析可以使用滑動視窗的原因）

方法三：構造前綴和數組，然後使用二分查找

第438 題：同第76 題；

第567 題：同第76 題，收集符合條件的語句不一樣而已。

二、雙指針

「雙指標」問題其實也是樸素演算法的最佳化，一下子排序掉很多不符合題意的解，「滑動視窗」技巧也是這樣的。還是分析為什麼可以使用雙指標是更重要的。

二分查找演算法應用於查找下標也可以認為是雙指標的解法。

第7 章鍊錶

解決鍊錶問題，很實用的技巧是「畫圖」。其它演算法問題的分析和講解（和麵試官講解）也是這樣。

可以為鍊錶編寫測試函數，方便調試。建議實現的方法有：① 透過陣列建立一個單鍊錶；② 根據目前結點列印目前結點以及後面的結點。這兩個方法可以非常方便地幫助我們調試關於鍊錶的程式。

題型一：基本的鍊錶指標指向問題

注意：有一些問題需要使用“虛擬頭結點”，以避免對鍊錶第一個結點的複雜的分類討論邏輯。這個想法在陣列裡我們見過，叫「哨兵」。

使用遞歸函數，避免複雜的更改指標變數指向操作，使得求解問題變得簡單。

說明：

題型二：快慢指針技巧

確切地說，叫「同步指針」可能會更好一些。

使用兩個指標變量，剛開始都位於鍊錶的第一個結點，一個永遠一次只走一步，另一個永遠一次只走兩步，一個在前，一個在後，同時走。這樣當快指針走完的時候，慢指針就來到了鍊錶的中間位置。

解決這些問題的共同特點就是使用兩個指標變數同步移動。快慢指針的前進方向相同，且它們步伐的「差」是恆定的，根據這種確定性去解決鍊錶中的一些問題。使用這種思想還可以解決鍊錶的以下問題：

說明：

題型三：設計資料結構

第8 章棧與佇列

一、堆疊

題型一：基本的使用堆疊解決的問題

下面的問題非常基礎，一定需要掌握：

練習：

題型二：單調棧

單調棧就是普通的棧，在使用的過程中恰好符合了「後進先出」，棧內元素單調的特徵。 「單調棧」和「單調佇列」的問題通常來說很特殊，掌握例題和一些練習就可以了。

經驗：單調棧中一般存下標。

說明：

練習：

二、隊列

題型一：基本的使用佇列解決的問題

所有的使用廣度優先遍歷解決的問題，都使用了佇列。

題型二：單調隊列

單調隊列就是普通的隊列。 「力扣」上的單調隊列目前就發現這一個問題，關鍵分析清楚為什麼設計的演算法恰好使得單調隊列。另外，「背包問題」有使用單調隊列進行最佳化的例子，有興趣的朋友可以了解一下，是競賽方面的知識。

經驗：單調隊列中一般存下標。

第9 章優先隊列

說明：了解「堆」作為「優先隊列」的實作是有必要的，有助於理解remove() 、replace() 這些編碼的細節，使用堆的時候才會更有效。

應用：動態選取目前佇列中優先權最高的元素，重點在於理解「動態」的意思。

第10 章並查集

並查集知識點的【影片講解】在第990 題視訊題解裡有。基礎且常見的問題有：

選做問題：

第11 章樹（二元樹與二分搜尋樹）

第12 章回溯演算法

題型一：基本回溯問題

透過這些問題理解回溯演算法的思想，回溯演算法的知識點講解在「力扣」第46 題的視訊題解和文字題解。

回溯就是用深度優先遍歷的方式去搜尋樹（圖）的所有解。深度優先遍歷有很明顯的遞歸結構。

做對以下這些問題的技巧：① 畫圖、畫圖、畫圖；② 理解深度優先遍歷與遞歸；③ 多調試、多調試。

題型二：字串上的回溯問題

重點理解：由於字串每次都產生新字符，因此無須狀態重置。

題型三：Flood Fill

題型四：一些遊戲問題

說明：

第13 章動態規劃（上）

動態規劃的兩個重要想法：

動態規劃的兩個思考方向：

可以使用動態規劃的解決問題需要具備的三個條件：

動態規劃的兩個重要概念：

問題分類參考：

說明：下面給出的典型問題也會被添加（2020 年12 月2 日）。

一、入門問題

了解「自頂向下」記憶化遞迴與「自底向上」遞推兩種動態規劃的方式。

二、重複子問題

這部分需要用到「逐步計數乘法原理」、「分類計數加法原理」。

第70 題：和斐波拉契數是同一題。計數類別問題會用到分類計數原理、逐步計數原理。

三、最優子結構

說明：

第377 題注意甄別不是背包問題。

四、無後效性

練習：

以下是一些“動態規劃”經典問題。因為這些問題很重要，所以單獨作為一個分類。

五、最大子段和

練習：

六、最長上升子序列

說明：第300 題是非常經典的動態規劃問題。 $O(N log N)$ 的解法，針對問題本身的特性進行狀態定義，並證明狀態數組是有序數組，降低了時間複雜度。

練習：

七、最長公共子串

八、區間DP 與劃分型DP

區間DP：

劃分型DP：

九、樹形DP

第14 章動態規劃（下）

一、背包問題

背包九講：https://github.com/tianyicui/pack

（會補充「博弈類型DP」、「狀態壓縮DP」、「數字DP」等。）

其它問題

第15 章貪心演算法

第17 章哈希表

第18 章前綴和與雜湊表

第19 章廣度優先遍歷

樹的廣度優先遍歷的一些問題、LeetBook 裡的一些問題。

第20 章圖論演算法（最小生成樹）

第21 章圖論演算法（單源最短路徑）

第22 章分治演算法

分治思想（分而治之）把一個規模較大的問題拆分成為若干個規模較小的相同類型的子問題，然後對這些子問題遞歸求解，等待每一個子問題完成以後，再得到原問題的解。

分治演算法可以並行執行，但是在基礎演算法領域，分治演算法是以深度優先遍歷的方式執行的。

應用分治思想的典型演算法：歸併排序、快速排序。

分治思想的典型問題：「劍指Offer 第51 題」：《劍指Offer》 51. 陣列中的逆序對（影片解說）。

其它典型問題（待添加）

也會繼續更新，歡迎朋友多提寶貴意見！