1??前言：追憶我的刷題經歷

??大學的時候比較瘋狂，除了上課的時候，基本都是在機房刷題，當然，有時候連上課都在想題目，紙上寫好代碼，一下課就沖進機房把代碼敲了，目的很單純，為了沖排行榜，就像玩游戲一樣，享受霸榜的快感，
??當年主要是在 杭電OJ （HDOJ） 和 北大OJ（POJ） 這兩個在線平臺上刷題，那時候應該還沒有（LeetCode、洛谷、牛客 這些主流的刷題網站），后來參加作業以后，剩余的時間不多了，也就沒怎么刷了， 但是 演算法思維 也就是靠上大學那四年鍛煉出來的，


??當年題目少，刷題的人也少，所以勉強還沖到過第一，現在去看已經 58 名了，可見 長江后浪推前浪，前浪 S 在沙灘上，時勢造英雄啊！

??北大人才輩出，相對題目也比較難，所以明顯有點 心有余而力不足 的感覺，刷的相對就少很多，而且這個 OJ 也沒什么人維護了，看我的簽名，當時竟然還想著給博客引點流，現在估計都沒什么人去那個網站了吧，如果有，記得評論區告訴我，一起緬懷一下逝去的青春，

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《畫解資料結構》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌

2??演算法和資料結構的重要性

👪1、適用人群

• 這篇文章會從 「演算法和資料結構」 零基礎開始講，所以，如果你是演算法大神，可以盡情在評論區嘲諷我哈哈，目的當然是幫助想要涉足演算法領域，或者正在找作業的朋友，以及將要找作業的大學生，更加有效快速的掌握演算法思維，能夠在職場面試和筆試中一展身手，
• 這篇文章中，我會著重講解一些常見的 「演算法和資料結構」 的設計思想，并且配上動圖，主要針對面試中常見的問題和新手朋友們比較難理解的點進行決議，當然，后面也會給出面向演算法競賽的提綱，如果有興趣深入學習的歡迎在評論區留言，一起成長交流，
• 零基礎學演算法的最好方法，莫過于刷題了，任何事情都是需要堅持的，刷題也一樣，沒有刷夠足夠的題，就很難做出系統性的總結，所以上大學的時候，我花了三年的時間來刷題， 作業以后還是會抽點時間出來刷題，

千萬不要用作業忙來找借口，時間擠一擠總是有的，

• 我現在上班地鐵上一個小時，下班地鐵又是一個小時，比如這篇文章的起草，就是在 地鐵 上完成的，如何利用這兩個小時的時間，做一些有建設性的事情，才是最重要的，刷抖音一個小時過得很快，刷題也是同樣的道理，
• 當然，每天不需要花太多時間在這個上面，把這個事情做成一個規劃，按照長期去推進，反正也沒有 KPI 壓力，就當成是作業之余的一種消遣，還能夠提升思維能力，

所以，無論你是 小學生，中學生，高中OIer，大學ACMer，職場人士，只要想開始，一切都不會太晚！

🎾2、有何作用

• 我們平常使用的 智能手機、搜索引擎、網站、作業系統、游戲、軟體、人工智能，都大量地應用了 「演算法與資料結構」 的知識，以及平時你用到的各種庫的底層實作，也是通過各種演算法和資料結構組合出來的，所以可以說，有程式的地方，就有江湖 演算法，有演算法就一定會有對應的資料結構，
• 如果你只是想學會寫代碼，或許 「演算法與資料結構」 并不是那么重要，但是想要往更深一步發展，「演算法與資料結構」 是必不可少的，

??現在一些主流的大廠，在面試快結束的時候都會 奉上一道演算法題，如果你敲不出來，可能你的 offer 年包就打了 七折，或者直接與 offer 失之交臂，都是有可能的（因為我自己也是萬惡的面試官，看到候選人的演算法題寫不出來我也是操碎了心，但是我一般會給足容錯，比如給三個演算法題，挑一個寫，任意寫出一個都行），

• 當然，它不能完全代表你的編碼能力，因為有些演算法確實是很巧妙，加上緊張的面試氛圍，想不出來其實也是正常的，但是你能確保面試官是這么想的嗎？我們要做的是十足的準備，既然決定出來，offer 當然是越高越好，畢竟大家都要養家糊口，房價又這么貴，如果能夠在演算法這一塊取得先機，也不失為一個捷徑，

所以，你問我演算法和資料結構有什么用？我可以很明確的說，和你的年薪息息相關，

• 當然，面試中 「演算法與資料結構」 知識的考察只是面試內容的一部分，其它還有很多面試要考察的內容，當然不是本文主要核心內容，這里就不做展開了，

📜3、演算法簡介

• 演算法是什么東西？
• 它是一種方法，一種解決問題的方案，
• 舉個例子，你現在要去上班，可以選擇 走路、跑步、坐公交、坐地鐵、自己開車 等等，這些都是解決方案，但是它們都會有一些衡量指標，讓你有一個權衡，最后選擇你認為最優的策略去做，
• 而衡量的指標諸如：時間消耗、金錢消耗、是否需要轉車、是否可達 等等，

時間消耗就對應了：時間復雜度
金錢消耗就對應了：空間復雜度
是否可達就對應了：演算法可行性

• 當然，是否需要轉車，從某種程度上都會影響 時間復雜度 或者 空間復雜度，

🌲4、資料結構

• 對于實作某個演算法，我們往往會用到一些資料結構，
• 因為我們通常不能一下子把資料處理完，更多的時候需要先把它們放在一個容器或者說快取里面，等到一定的時刻再把它們拿出來，
• 這其實是一種 「空間換時間」 思想的體現， 恰當使用資料結構可以幫助我們高效地處理資料，
• 常用的一些資料結構如下：

• 為什么需要引入這么多資料結構呢？

??答案是：任何一種資料結構是不是 完美的，所以我們需要根據對應的場景，來采用對應的資料結構，具體用哪種資料結構，需要通過刷題不斷重繪經驗，才能總結出來，

3??如何開始持續的刷題

• 有朋友告訴我，題目太難了，根本不會做，每次都是看別人的解題報告，

📑1、立軍令狀

• 所謂 「軍令狀」，其實就是給自己定一個目標，給自己樹立一個目標是非常重要的，有 「目標才會有方向，有目標才會有動力，有目標才會有人生的意義」 ，而軍令狀是貶義的，如果不達成就會有各種懲罰，所以其實你是心不甘情不愿的，于是這件事情其實是無法持久下去的，

事實證明，立軍令狀是不可取的，

• 啊這……所以我們還是要采用一些能夠持久下去的方法，

👩????👩2、培養興趣

• 為了讓這件事情能夠持久下去，一定要培養出興趣，適時的給自己一些正反饋，正反饋的作用就是每過一個周期，如果效果好，就要有獎勵，這個獎勵機制可以自己設定，但是 「不能作弊」 ，一旦作弊就像單機游戲修改數值，流失是遲早的事，
• 舉個例子，我們可以給每天制定一些 「不一樣的目標和獎勵」 ，比如下圖所示：

• 當然，這個完成獎勵你可以自己定，總而言之，要是對你有傭訓的獎勵才是有意義的，

🚿3、狂切水題

• 剛開始刷的 300 題一定都是 「水題」 ，刷 「水題」 的目的是讓你養成一個每天刷題的習慣，久而久之，不刷題的日子會變得無比煎熬，當然，刷著刷著，你會發現，水題會越來越多，因為刷題的程序中，你已經無形中不斷成長起來了，
• 至少這個方法我用過，非常靈驗！推薦刷題從水題開始，

如果不知道哪里有水題，推薦：
?? C語言入門水題：《C語言入門100例》
??C語言演算法水題：《LeetCode演算法全集》

💪🏻4、養成習慣

• 相信如果切了 300 個 「水題」 以后，刷題自然而然就成了習慣，想放棄都難，這個專業上講，其實叫 沉沒成本，有興趣的可以自行百度，這里就不再累述了，

🈵5、一周出師

• 基本上如果能夠按照這樣的計劃去執行，一周以后，一定會有識訓，沒有識訓的話，可以來找我，

4??簡單資料結構的掌握

🚂1、陣列

記憶體結構：記憶體空間連續
實作難度：簡單
下標訪問：支持
分類：靜態陣列、動態陣列
插入時間復雜度： O ( n ) O(n) O(n)
查找時間復雜度： O ( n ) O(n) O(n)
洗掉時間復雜度： O ( n ) O(n) O(n)

🎫2、字串

記憶體結構：記憶體空間連續，類似字符陣列
實作難度：簡單，一般系統會提供一些方便的字串操作函式
下標訪問：支持
插入時間復雜度： O ( n ) O(n) O(n)
查找時間復雜度： O ( n ) O(n) O(n)
洗掉時間復雜度： O ( n ) O(n) O(n)

🎇3、鏈表

記憶體結構：記憶體空間連續不連續，看具體實作
實作難度：一般
下標訪問：不支持
分類：單向鏈表、雙向鏈表、回圈鏈表、DancingLinks
插入時間復雜度： O ( 1 ) O(1) O(1)
查找時間復雜度： O ( n ) O(n) O(n)
洗掉時間復雜度： O ( 1 ) O(1) O(1)

🌝4、哈希表

記憶體結構：哈希表本身連續，但是衍生出來的結點邏輯上不連續
實作難度：一般
下標訪問：不支持
分類：正數哈希、字串哈希、滾動哈希
插入時間復雜度： O ( 1 ) O(1) O(1)
查找時間復雜度： O ( 1 ) O(1) O(1)
洗掉時間復雜度： O ( 1 ) O(1) O(1)

• 哈希表相關的內容，可以參考我的這篇文章：
• 夜深人靜寫演算法（九）- 哈希表

👨?👩?👧5、佇列

記憶體結構：看用陣列實作，還是鏈表實作
實作難度：一般
下標訪問：不支持
分類：FIFO、單調佇列、雙端佇列
插入時間復雜度： O ( 1 ) O(1) O(1)
查找時間復雜度：理論上不支持
洗掉時間復雜度： O ( 1 ) O(1) O(1)

• 佇列相關的內容，可以參考我的這篇文章：
• 夜深人靜寫演算法（十）- 單向廣搜

👩?👩?👦?👦6、堆疊

記憶體結構：看用陣列實作，還是鏈表實作
實作難度：一般
下標訪問：不支持
分類：FILO、單調堆疊
插入時間復雜度： O ( 1 ) O(1) O(1)
查找時間復雜度：理論上不支持
洗掉時間復雜度： O ( 1 ) O(1) O(1)

• 堆疊相關的內容，可以參考我的這篇文章：
• 夜深人靜寫演算法（十一）- 單調堆疊

🌵7、二叉樹

優先佇列 是 堆實作的，所以也屬于 二叉樹 范疇，它和佇列不同，不屬于線性表，
記憶體結構：記憶體結構一般不連續，但是有時候實作的時候，為了方便，一般是物理連續，邏輯不連續
實作難度：較難
下標訪問：不支持
分類：二叉樹 和 多叉樹
插入時間復雜度：看情況而定
查找時間復雜度：理論上 O ( l o g 2 n ) O(log_2n) O(log2?n)
洗掉時間復雜度：看情況而定

🌳8、多叉樹

記憶體結構：記憶體結構一般不連續，但是有時候實作的時候，為了方便，一般是物理連續，邏輯不連續
實作難度：較難
下標訪問：不支持
分類：二叉樹 和 多叉樹
插入時間復雜度：看情況而定
查找時間復雜度：理論上 O ( l o g 2 n ) O(log_2n) O(log2?n)
洗掉時間復雜度：看情況而定

• 一種經典的多叉樹是字典樹，可以參考我的這篇文章：
• 夜深人靜寫演算法（七）- 字典樹

🌲9、森林

• 比較經典的森林是：并查集，可以參考我的這篇文章：
• 夜深人靜寫演算法（五）- 并查集

🍀10、樹狀陣列

• 樹狀陣列是用來做 單點更新，成端求和 的問題的，有關于它的內容，可以參考：
• 夜深人靜寫演算法（十三）- 樹狀陣列

🌍11、圖

記憶體結構：不一定
實作難度：難
下標訪問：不支持
分類：有向圖、無向圖
插入時間復雜度：根據演算法而定
查找時間復雜度：根據演算法而定
洗掉時間復雜度：根據演算法而定

1、圖的概念

• 在講解最短路問題之前，首先需要介紹一下計算機中圖（圖論）的概念，如下：
• 圖 G G G 是一個有序二元組 ( V , E ) (V,E) (V,E)，其中 V V V 稱為頂點集合， E E E 稱為邊集合， E E E 與 V V V 不相交，頂點集合的元素被稱為頂點，邊集合的元素被稱為邊，
• 對于無權圖，邊由二元組 ( u , v ) (u,v) (u,v) 表示，其中 u , v ∈ V u, v \in V u,v∈V，對于帶權圖，邊由三元組 ( u , v , w ) (u,v, w) (u,v,w) 表示，其中 u , v ∈ V u, v \in V u,v∈V， w w w 為權值，可以是任意型別，
• 圖分為有向圖和無向圖，對于有向圖， ( u , v ) (u, v) (u,v) 表示的是 從頂點 u u u 到 頂點 v v v 的邊，即 u → v u \to v u→v；對于無向圖， ( u , v ) (u, v) (u,v) 可以理解成兩條邊，一條是 從頂點 u u u 到 頂點 v v v 的邊，即 u → v u \to v u→v，另一條是從頂點 v v v 到 頂點 u u u 的邊，即 v → u v \to u v→u；

2、圖的存盤

• 對于圖的存盤，程式實作上也有多種方案，根據不同情況采用不同的方案，接下來以圖二-3-1所表示的圖為例，講解四種存盤圖的方案，
  

1）鄰接矩陣

• 鄰接矩陣是直接利用一個二維陣列對邊的關系進行存盤，矩陣的第 i i i 行第 j j j 列的值 表示 i → j i \to j i→j 這條邊的權值；特殊的，如果不存在這條邊，用一個特殊標記 ∞ \infty ∞ 來表示；如果 i = j i = j i=j，則權值為 0 0 0，
• 它的優點是：實作非常簡單，而且很容易理解；缺點也很明顯，如果這個圖是一個非常稀疏的圖，圖中邊很少，但是點很多，就會造成非常大的記憶體浪費，點數過大的時候根本就無法存盤，
• [ 0 ∞ 3 ∞ 1 0 2 ∞ ∞ ∞ 0 3 9 8 ∞ 0 ] \left[ \begin{matrix} 0 & \infty & 3 & \infty \\ 1 & 0 & 2 & \infty \\ \infty & \infty & 0 & 3 \\ 9 & 8 & \infty & 0 \end{matrix} \right] ?????01∞9?∞0∞8?320∞?∞∞30??????

2）鄰接表

• 鄰接表是圖中常用的存盤結構之一，采用鏈表來存盤，每個頂點都有一個鏈表，鏈表的資料表示和當前頂點直接相鄰的頂點的資料 ( v , w ) (v, w) (v,w)，即 頂點 和 邊權，
• 它的優點是：對于稀疏圖不會有資料浪費；缺點就是實作相對鄰接矩陣來說較麻煩，需要自己實作鏈表，動態分配記憶體，
• 如圖所示， d a t a data data 即 ( v , w ) (v, w) (v,w) 二元組，代表和對應頂點 u u u 直接相連的頂點資料， w w w 代表 u → v u \to v u→v 的邊權， n e x t next next 是一個指標，指向下一個 ( v , w ) (v, w) (v,w) 二元組，
  
• 在 C++ 中，還可以使用 vector 這個容器來代替鏈表的功能；

    vector<Edge> edges[maxn];

3）前向星

• 前向星是以存盤邊的方式來存盤圖，先將邊讀入并存盤在連續的陣列中，然后按照邊的起點進行排序，這樣陣列中起點相等的邊就能夠在陣列中進行連續訪問了，
• 它的優點是實作簡單，容易理解；缺點是需要在所有邊都讀入完畢的情況下對所有邊進行一次排序，帶來了時間開銷，實用性也較差，只適合離線演算法，
• 如圖所示，表示的是三元組 ( u , v , w ) (u, v, w) (u,v,w) 的陣列， i d x idx idx 代表陣列下標，
  
• 那么用哪種資料結構才能滿足所有圖的需求呢？
• 接下來介紹一種新的資料結構 —— 鏈式前向星，

4）鏈式前向星

• 鏈式前向星和鄰接表類似，也是鏈式結構和陣列結構的結合，每個結點 i i i 都有一個鏈表，鏈表的所有資料是從 i i i 出發的所有邊的集合（對比鄰接表存的是頂點集合），邊的表示為一個四元組 ( u , v , w , n e x t ) (u, v, w, next) (u,v,w,next)，其中 ( u , v ) (u, v) (u,v) 代表該條邊的有向頂點對 u → v u \to v u→v， w w w 代表邊上的權值， n e x t next next 指向下一條邊，
• 具體的，我們需要一個邊的結構體陣列 edge[maxm]，maxm表示邊的總數，所有邊都存盤在這個結構體陣列中，并且用head[i]來指向 i i i 結點的第一條邊，
• 邊的結構體宣告如下：

struct Edge {
    int u, v, w, next;
    Edge() {}
    Edge(int _u, int _v, int _w, int _next) :
        u(_u), v(_v), w(_w), next(_next) 
    {
    }
}edge[maxm];

• 初始化所有的head[i] = -1，當前邊總數 edgeCount = 0；
• 每讀入一條 u → v u \to v u→v 的邊，呼叫 addEdge(u, v, w)，具體函式的實作如下：

void addEdge(int u, int v, int w) {
    edge[edgeCount] = Edge(u, v, w, head[u]);
    head[u] = edgeCount++;
}

• 這個函式的含義是每加入一條邊 ( u , v , w ) (u, v, w) (u,v,w)，就在原有的鏈表結構的首部插入這條邊，使得每次插入的時間復雜度為 O ( 1 ) O(1) O(1)，所以鏈表的邊的順序和讀入順序正好是逆序的，這種結構在無論是稠密的還是稀疏的圖上都有非常好的表現，空間上沒有浪費，時間上也是最小開銷，
• 呼叫的時候只要通過head[i]就能訪問到由 i i i 出發的第一條邊的編號，通過編號到edge陣列進行索引可以得到邊的具體資訊，然后根據這條邊的next域可以得到第二條邊的編號，以此類推，直到 next域為 -1 為止，

for (int e = head[u]; ~e; e = edges[e].next) {
    int v = edges[e].v;
    ValueType w = edges[e].w;
    ...
}

• 文中的 ~e等價于 e != -1，是對e進行二進制取反的操作（-1 的的補碼二進制全是 1，取反后變成全 0，這樣就使得條件不滿足跳出回圈），

5??簡單演算法的入門

• 入門十大演算法是 線性列舉、線性迭代、簡單排序、二分列舉、雙指標、差分法、位運算、貪心、分治遞回、簡單動態規劃，
• 對于這十大演算法，我會逐步更新道這個專欄里面：《LeetCode演算法全集》，
• 濃縮版可參考如下文章：《十大入門演算法》

🚊10、簡單動態規劃

LeetCode 746. 使用最小花費爬樓梯

??陣列的每個下標作為一個階梯，第 i i i 個階梯對應著一個非負數的體力花費值 c o s t [ i ] cost[i] cost[i]（下標從 0 開始），每當爬上一個階梯，都要花費對應的體力值，一旦支付了相應的體力值，就可以選擇 向上爬一個階梯 或者 爬兩個階梯，求找出達到樓層頂部的最低花費，在開始時，可以選擇從下標為 0 或 1 的元素作為初始階梯，
??樣例輸入： c o s t = [ 1 , 99 , 1 , 1 , 1 , 99 , 1 , 1 , 99 , 1 ] cost = [1, 99, 1, 1, 1, 99, 1, 1, 99, 1] cost=[1,99,1,1,1,99,1,1,99,1]
??樣例輸出： 6 6 6
如圖所以，藍色的代表消耗為 1 的樓梯，紅色的代表消耗 99 的樓梯，

a、思路分析

• 令走到第 i i i 層的最小消耗為 f [ i ] f[i] f[i]
• 假設當前的位置在 i i i 層樓梯，那么只可能從 i ? 1 i-1 i?1 層過來，或者 i ? 2 i-2 i?2 層過來；
• 如果從 i ? 1 i-1 i?1 層過來，則需要消耗體力值： f [ i ? 1 ] + c o s t [ i ? 1 ] f[i-1] + cost[i-1] f[i?1]+cost[i?1]；
• 如果從 i ? 2 i-2 i?2 層過來，則需要消耗體力值： f [ i ? 2 ] + c o s t [ i ? 2 ] f[i-2] + cost[i-2] f[i?2]+cost[i?2]；
• 起點可以在第 0 或者 第 1 層，于是有狀態轉移方程：
• f [ i ] = { 0 i = 0 , 1 min ? ( f [ i ? 1 ] + c o s t [ i ? 1 ] , f [ i ? 2 ] + c o s t [ i ? 2 ] ) i > 1 f[i] = \begin{cases} 0 & i=0,1\\ \min ( f[i-1] + cost[i-1], f[i-2] + cost[i-2] ) & i > 1\end{cases} f[i]={0min(f[i?1]+cost[i?1],f[i?2]+cost[i?2])?i=0,1i>1?
  

b. 時間復雜度

• 狀態數： O ( n ) O(n) O(n)
• 狀態轉移： O ( 1 ) O(1) O(1)
• 時間復雜度： O ( n ) O(n) O(n)

c. 代碼詳解

class Solution {
    int f[1100];                                                   // (1)
public:
    int minCostClimbingStairs(vector<int>& cost) {
        f[0] = 0, f[1] = 0;                                        // (2)
        for(int i = 2; i <= cost.size(); ++i) {
            f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2]);    // (3)
        }
        return f[cost.size()];
    }
};

• ( 1 ) (1) (1) 用f[i]代表到達第 i i i 層的消耗的最小體力值，
• ( 2 ) (2) (2) 初始化；
• ( 3 ) (3) (3) 狀態轉移；

有沒有發現，這個問題和斐波那契數列很像，只不過斐波那契數列是求和，這里是求最小值，

6??刷題順序的建議

??然后介紹一下刷題順序的問題，我們刷題的時候千萬不要想著一步到位，一開始，沒有刷滿三百題，姿態放低，都把自己當成小白來處理，
??這里以刷 LeetCode 為例，我目前只刷了不到 50 題，所以我是小白，
??當我是小白時，我只刷入門題，也就是下面這幾個專題，先把上面所有的題目刷完，在考慮下一步要做什么，

👨?👦1、入門演算法

??當入門的題刷完了，并且都能講述出來自己刷題的程序以后，我們再來看初級的一些演算法和簡單的資料結構，簡單的資料結構就是線性表了，包含：陣列、字串、鏈表、堆疊、佇列 等等，即下面這些專題，

👩?👧?👦2、初級演算法

??上面的題刷完以后，其實已經算是基本入門了，然后就可以開始系統性的學習了，
??當然，基本如果真的到了這一步，說明你的確已經愛上了刷題了，那么我們可以嘗試挑戰一下 LeetCode 上的一些熱門題，畢竟熱門題才是現在面試的主流，能夠有更好的結果，這樣刷題的時候也會有更加強勁的動力不是嗎！

👩?👩?👧?👦3、中級演算法

7??系統學習演算法和資料結構

🚍1、進階動態規劃

🪐2、強勁圖論搜索

1、深度優先搜索

2、廣度優先搜索

0??3、進階初等數論

🛑4、進階計算幾何

📏5、字串的匹配

🎄6、高級資料結構

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《畫解資料結構》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌