耗時兩週，我整理了一套資料結構與演算法的學習路線，大廠面試不再困難！

對於我們程式設計師來說，資料結構和演算法是必須要掌握的內功。網路上有很多人整理過程式設計學習的路線圖，但是有關資料結構和演算法的卻並不多。

為了能夠幫助到更多的程式設計師小夥伴，小灰花了整整兩週時間，整理了一份資料結構和演算法的學習路線圖。

這份路線圖包含了115項重要的知識點，可以說是非常的全面，而且大部分知識點都附上了詳細的講解，這些講解都是我最近五年以來陸陸續續寫的原創內容。

這份路線圖包含了四大部分，分別是

資料結構基礎

、

演算法基礎

、

常見面試題

，以及各種

學習工具

。由於這張路線圖比較複雜，乍一看可能會感到懵逼，因此小灰特意帶著大家來導讀一下：

1.資料結構基礎

資料結構當中最基本也是最常用的一類，是

線性資料結構

，其中包括大家最熟悉的

陣列

和

連結串列

。透過這兩種基礎資料結構，又可以實現出

棧

和

隊

列。這幾種資料結構的特性和原理，大家一定要掌握，最好是能自己用程式碼實現出它們的基本功能，面試常考。

除了線性資料結構以外，

樹

也是比較常用的資料結構，其中最核心的是二叉樹。

手寫二叉樹的遍歷

，常常在面試中被考察，其中深度遍歷比較簡單，寫個遞迴就行，層序遍歷稍微複雜一些，實現的時候需要懂一些腦筋。

二叉樹根據不同功能，又分成了很多具體的資料結構，最基礎的是

二叉查詢樹

，可以方便元素的查詢和排序。

AVL樹

和

紅黑樹

，是二叉查詢樹的特殊形式，可以在多次插入刪除節點之後，仍然保持樹的平衡。

二叉堆

也是一種特殊的二叉樹，分為大頂堆和小頂堆，可以始終保證堆頂的元素是最大或者最小的一個，

堆排序演算法

和

優先順序佇列

都用到了這個資料結構。

還有一種很有趣的二叉樹，叫做

哈夫曼樹

。它的功能是把通訊報文的字元轉化成哈夫曼編碼，從而壓縮通訊報文的總長度。

除了二叉樹之外，我們工作中也會用到一些非二叉樹，最常用的就是

B-樹

和

B+樹

。我們電腦上檔案系統的索引，很多就是用B-樹實現的，而我們常用的關係型資料庫，預設索引就是用B+樹實現。

此外，還有一種叫做

字首樹

的結構，可以透過單詞的字首來快速匹配到我們想要查詢的單詞。

說完了樹結構，我們再來說一說

圖

。圖這種資料結構，相對來說不算是很常用，我們對它有一個基本的瞭解就可以。

首先我們要知道，圖可以按照兩個維度來劃分，

有向圖

和

無向圖

，

帶權圖

和

無權圖

。

其次，圖的遍歷有兩種方式，

廣度優先遍歷

和

深度優先遍歷

。

圖結構會使用到一類重要的演算法：

最短路徑演算法

。其中

Dijkstra演算法

可以求出某頂點到另一個頂點的最短路徑，也就是單源最短路徑；

Floyd演算法

可以求出所有頂點到某一頂點的最短路徑，也就是多源最短路徑。

另外，

最小生成樹

大家也可以瞭解一下，它是圖的一部分，保證所有頂點都連通的情況下，總成本最小。

除了上面講的這些資料結構以外，還有一些複合資料結構也很重要。

比如大家最熟悉的

雜湊表

，是陣列與連結串列的結合，大家需要了解雜湊表的基本原理，以及如何解決

雜湊衝突

。這個大廠面試必考。

除了雜湊表以外，

雜湊連結串列

也很常用。我們Redis資料庫當中用到的

LRU演算法

，背後就用到了雜湊連結串列。

還有兩種複合資料結構可能知道的人不多，一個是

跳錶

，它在連結串列的基礎上增加了很多層級，主要為了提升連結串列的查詢效率。另一個是

線段樹

，他是陣列和二叉樹的結合，方便在區域性範圍內對陣列進行操作。

2.演算法基礎

資料結構基礎就說到這裡，接下來我們說一說演算法基礎。要學習演算法，首先要弄懂演算法到底是什麼，同時也要理解衡量演算法好壞的重要指標：

時間複雜度

和

空間複雜度

。

排序演算法

，可以說是程式設計師最常用的一類演算法。

排序演算法同樣可以按照不同的維度進行分類，以相等元素的位置是否改變作為條件，可以分成

穩定排序

和

不穩定排序

；以排序過程是否在記憶體中完成為條件，可以分成

內部排序

和

外部排序。

以時間複雜度為條件，又可以劃分為更多的型別，時間複雜度O（n^2）的排序，包括

氣泡排序

、

選擇排序

、

插入排序

；O（nlogn）的排序，包括

快速排序

、

歸併排序

、

堆排序

、

錦標賽排序

；線性時間複雜度的排序，包括

計數排序

，

桶排序

，

基數排序

。至於

希爾排序

的時間複雜度比較特殊，取決於每一輪分組的方式。最後，還有一些排序演算法沒有什麼實用性，純粹是用來搞笑的，比如

猴子排序

、

睡眠排序

，以及

珠排序

。

除了排序演算法以外，

查詢演算法

也非常常用。想要在一個數組當中查詢到某個元素，我們可以使用

二分查詢

。同時，二分查詢也可以有進一步的最佳化，未必每一次查詢都要選擇中間位置。

那麼，想要在連結串列當中查詢元素怎麼辦呢？剛才講資料結構的時候說過，可以使用跳錶來解決。

還有一個很常見的場景，就是在一段文本當中查詢某個關鍵詞，這就需要用到

字串匹配演算法

。比較高效的字串匹配演算法有

RK演算法

、

BM演算法

、

KMP演算法

，這些演算法只要有基本瞭解即可，正常的面試官不太可能讓你手寫出來。

還有一類演算法，可以為複雜的問題提供最優的解決方案。在某些場景下，比如針對部分揹包問題，我們可以用

貪心演算法

這樣簡單粗暴的演算法來求解；但是貪心演算法有它的侷限性，有些場景下我們不得不使用

動態規劃演算法

來求解。動態規劃是演算法領域的難點和重點，已有一定演算法基礎的小夥伴，最好能把這個知識點給搞明白。

此外，還有一類演算法比較常用，那就是網路安全演算法。其中包括

AES演算法

、

RSA演算法

這樣的

加密演算法

，也包括

MD5演算法

、

SHA演算法

這樣的

雜湊演算法

。很多人以為MD5演算法以及SHA演算法是加密演算法，這個認知是錯誤的。

另外，我們每天訪問網路都會用到的

HTTPS協議

，是對眾多加密演算法與雜湊演算法的綜合運用。

3.面試題與學習工具

說完了資料結構基礎，我們再來說一說面試題。在這裡，我總結出了21道大廠常見的演算法面試題，其中大部分面試題出自LeetCode網站，我這裡也標註了對應的LeetCode題號。

面試題按照難度，分成了簡單中等、困難三個級別。每一道題後面都附帶了我的原創講解。大家可以從簡單題開始入手，後面再逐漸加大難度。

最後，我也介紹一些比較好的資料結構和演算法學習工具。首先一個重要的學習工具，就是圖書。路線圖裡列出了幾本比較暢銷的演算法圖書，有國內的也有國外的，對於入門的小夥伴，推薦看看小灰自己出的書，

《漫畫演算法》

系列。

其次，網上也有很多講解演算法影片課程，其中比較推薦極客時間王爭老師的演算法課，以及左程雲老師的課程，講的都比較深入淺出。

此外還有一些比較好的演算法學習和訓練網站。最有名的就是

LeetCode

，上面有上千道演算法題可以去刷，還可以看到別人的各種解法。還有一個網站叫

VisuAlgo

，上面有很多演算法與資料結構的視覺化演示，非常的形象生動，可以加深理解。

好了，關於資料結構與演算法的學習路線圖，我就為大家介紹到這裡。大家可以在【程式設計師小灰】的公眾號後臺

回覆關鍵詞“演算法學習”

，獲取更加完整清晰的路線圖。

如果覺得這套學習路線圖對你稍微有點幫助的話，希望可以

點個贊

。我是程式設計師小灰，祝大家在新的一年裡更上一層樓，感謝大家！