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、資料結構

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

資料結構	應用場景
陣列	線性存盤、元素為任意相同型別、隨機訪問
字串	線性存盤、元素為字符、結尾字符、隨機訪問
鏈表	鏈式存盤、快速洗掉
堆疊	先進后出
佇列	先進先出
哈希表	隨機存盤、快速增刪改查
二叉樹	對數時間增刪改查，二叉查找樹、線段樹
多叉樹	B/B+樹 硬碟樹、字典樹 字串前綴匹配
森林	并查集 快速合并資料
樹狀陣列	單點更新，成段求和

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

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

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

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

📑1、立軍令狀

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

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

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

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

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

刷題的第?天	目標題數	是否完成	完成獎勵
1	1	？	攻擊力 + 10
2	1	？	防御力 + 10
3	2	？	出去吃頓好的
4	2	？	攻擊力 + 29
5	3	？	防御力 + 60
6	1	？	攻擊力 + 20
7	4	？	出去吃頓好的
8	1	？	防御力 + 50

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

🚿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演算法全集》，

💨1、線性列舉

• 列舉一般可以理解成一個回圈，具體回圈里面做什么事情，要根據實際問題而定，舉個例子：

LeetCode 344. 反轉字串

??【例題1】撰寫一個函式，將輸入的字串反轉過來，輸入字串以字符陣列 char[] 的形式給出，必須原地修改輸入陣列、使用 O ( 1 ) O(1) O(1) 的額外空間解決這一問題，
??樣例輸入： [ ‘ ’ a ” , “ b ” , “ c ” ] [‘’a”, “b”, “c”] [‘’a”,“b”,“c”]
??樣例輸出： [ “ c ” , “ b ” , “ a ” ] [ “c”, “b”, “a”] [“c”,“b”,“a”]

a. 思路分析

??翻轉的含義，相當于就是 第一個字符 和 最后一個交換，第二個字符 和 最后第二個交換，… 以此類推，所以我們首先實作一個交換變數的函式 swap，然后再列舉 第一個字符、第二個字符、第三個字符 …… 即可，
??對于第 i i i 個字符，它的交換物件是 第 l e n ? i ? 1 len-i-1 len?i?1 個字符 (其中 l e n len len 為字串長度)，swap函式的實作，可以參考：《C語言入門100例》 - 例2 | 交換變數，

b. 時間復雜度

• 線性列舉為 O ( n ) O(n) O(n)，交換變數為 O ( 1 ) O(1) O(1)，兩個程序是相乘的關系，所以整個演算法的時間復雜度為 O ( n ) O(n) O(n)，

c. 代碼詳解

class Solution {
public:
    void swap(char& a, char& b) {            // (1)
        char tmp = a;
        a = b;
        b = tmp;
    }
    void reverseString(vector<char>& s) {
        int len = s.size();
        for(int i = 0; i < len / 2; ++i) {   // (2)
            swap(s[i], s[len-i-1]);
        }
    }
};

• ( 1 ) (1) (1) 實作一個變數交換的函式，其中&是C++中的參考，在函式傳參是經常用到，被稱為：參考傳遞(pass-by-reference)，即被調函式的形式引數雖然也作為區域變數在堆疊中開辟了記憶體空間
  ，但是這時存放的是由主調函式放進來的實參變數的地址，被調函式對形參的任何操作都被處理成間接尋址，即通過堆疊中存放的地址訪問主調函式中的實參變數，

簡而言之，函式呼叫的引數，可以傳參考，從而使得函式回傳時，傳參值的改變依舊生效，

• ( 2 ) (2) (2) 這一步是做的線性列舉，注意列舉范圍是 [ 0 , l e n / 2 ? 1 ] [0, len/2-1] [0,len/2?1]，

---

🥖2、線性迭代

• 每一次對程序的重復稱為一次 “迭代”，而每一次迭代得到的結果會作為下一次迭代的初始值，周而復始，直到問題全部解決，

LeetCode 206. 反轉鏈表

??【例題2】給定單鏈表的頭節點 h e a d head head ，要求反轉鏈表，并回傳反轉后的鏈表頭，
??樣例輸入： [ 1 , 2 , 3 , 4 ] [1,2,3,4] [1,2,3,4]
??樣例輸出： [ 4 , 3 , 2 , 1 ] [4, 3, 2, 1] [4,3,2,1]

• c++ 版本給出的基礎框架代碼如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
    }
};

• 這里引入了一種資料結構 鏈表 ListNode；
• 成員有兩個：資料域val和指標域next，
• 回傳的是鏈表頭結點；

a. 思路分析

• 這個問題，我們可以采用頭插法，即每次拿出第 2 個節點插到頭部，拿出第 3 個節點插到頭部，拿出第 4 個節點插到頭部，… 拿出最后一個節點插到頭部，
• 于是整個程序可以分為兩個步驟：洗掉第 i i i 個節點，將它放到頭部，反復迭代 i i i 即可，
• 如圖所示：
  
• 我們發現，圖中的藍色指標永遠固定在最開始的鏈表頭結點上，那么可以以它為貧訓，每次洗掉它的next，并且插到最新的頭結點前面，不斷改變頭結點head的指向，迭代 n ? 1 n-1 n?1 次就能得到答案了，

b. 時間復雜度

• 每個結點只會被訪問一次，執行一次頭插操作，總共 n n n 個節點的情況下，時間復雜度 O ( n ) O(n) O(n)，

c. 代碼詳解

class Solution {
    ListNode *removeNextAndReturn(ListNode* now) {                 // (1) 
        if(now == nullptr || now->next == nullptr) {
            return nullptr;                                        // (2) 
        }
        ListNode *retNode = now->next;                             // (3) 
        now->next = now->next->next;                               // (4) 
        return retNode;
    }
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *doRemoveNode = head;                             // (5) 
        while(doRemoveNode) {                                      // (6) 
            ListNode *newHead = removeNextAndReturn(doRemoveNode); // (7) 
            if(newHead) {                                          // (8) 
                newHead->next = head;                              
                head = newHead;                
            }else {
                break;                                             // (9) 
            }
        }
        return head;
    }
};

• ( 1 ) (1) (1) ListNode *removeNextAndReturn(ListNode* now)函式的作用是洗掉now的next節點，并且回傳；
• ( 2 ) (2) (2) 本身為慷訓者下一個節點為空，回傳空；
• ( 3 ) (3) (3) 將需要洗掉的節點快取起來，供后續回傳；
• ( 4 ) (4) (4) 執行洗掉 now->next 的操作；
• ( 5 ) (5) (5) doRemoveNode指向的下一個節點是將要被洗掉的節點，所以doRemoveNode需要被快取起來，不然都不知道怎么進行洗掉；
• ( 6 ) (6) (6) 沒有需要洗掉的節點了就結束迭代；
• ( 7 ) (7) (7) 洗掉 doRemoveNode 的下一個節點并回傳被洗掉的節點；
• ( 8 ) (8) (8) 如果有被洗掉的節點，則插入頭部；
• ( 9 ) (9) (9) 如果沒有，則跳出迭代，
  

---

💤3、簡單排序

• 既然是入門，千萬不要去看快排、希爾排序這種冷門排序，
• 冒泡排序、選擇排序、簡單插入排序 原理好懂，先看懂再說，其他不管，因為這三者都是基于列舉的，
• C中有現成qsort排序函式，C++中有現成 sort排序函式，直接拿來用，等演算法進階時再回頭來看快速排序的演算法實作，

【例題3】LeetCode 88. 合并兩個有序陣列

??【例題3】給你兩個有序整數陣列 n u m s 1 nums1 nums1 和 n u m s 2 nums2 nums2，請你將 n u m s 2 nums2 nums2 合并到 n u m s 1 nums1 nums1 中，使 n u m s 1 nums1 nums1 成為一個有序陣列，初始化 n u m s 1 nums1 nums1 和 n u m s 2 nums2 nums2 的元素數量分別為 m m m 和 n n n ，你可以假設 n u m s 1 nums1 nums1 的空間大小等于 m + n m + n m+n，這樣它就有足夠的空間保存來自 n u m s 2 nums2 nums2 的元素，
??樣例輸入： n u m s 1 = [ 1 , 2 , 3 , 0 , 0 , 0 ] , m = 3 , n u m s 2 = [ 2 , 5 , 6 ] , n = 3 nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 nums1=[1,2,3,0,0,0],m=3,nums2=[2,5,6],n=3
??樣例輸出： [ 1 , 2 , 2 , 3 , 5 , 6 ] [1,2,2,3,5,6] [1,2,2,3,5,6]

a. 思路分析

這個題別想太多，直接把第二個陣列的元素加到第一個陣列元素的后面，然后直接排序就成，

b. 時間復雜度

• STL 排序函式的時間復雜度為 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n)，遍歷的時間復雜度為 O ( n ) O(n) O(n)，所以總的時間復雜度為 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n)，

c. 代碼詳解

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i = m; i < n + m; ++i) {
            nums1[i] = nums2[i-m];               // (1)
        }
        sort(nums1.begin(), nums1.end());        // (2)
    }
};

• ( 1 ) (1) (1) 簡單合并兩個陣列；
• ( 2 ) (2) (2) 對陣列1進行排序；

只要能夠達到最終的結果， O ( n ) O(n) O(n) 和 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n) 的差距其實并沒有那么大，

---

🥂4、二分列舉

• 二分一般指二分查找，當然有時候也指代二分列舉，

LeetCode 704. 二分查找

??【例題4】給定 n ( 1 ≤ n ≤ 1 0 4 ) n(1 \le n \le 10^4) n(1≤n≤104) 個元素的升序整型陣列 n u m s nums nums 和一個值 t a r g e t target target，求實作一個函式查找 n u m s nums nums 中 t a r g e t target target 的下標，如果查找不到則回傳 ? 1 -1 ?1，

• c++ 版本給出的基礎框架代碼如下，要求實作的是search這個函式，陣列引數傳入的是一個vector<int>，是 STL 中常用的陣列容器，支持動態擴容，vector的動態擴容有興趣了解的，可以參考以下這篇文章：《C/C++ 面試 100 例》（四）vector 擴容策略，

class Solution {
public:
    int search(vector<int>& nums, int target) {
    }
};

a. 思路分析

• 1）令初始情況下，陣列下標從 0 開始，且陣列長度為 n n n，則定義一個區間，它的左端點是 l = 0 l=0 l=0，右端點是 r = n ? 1 r = n-1 r=n?1；
• 2）生成一個區間中點 m i d = ( l + r ) / 2 mid = (l + r) / 2 mid=(l+r)/2，并且判斷 m i d mid mid 對應的陣列元素和給定的目標值的大小關系，主要有三種：
• ??2.a）目標值 等于 陣列元素，直接回傳 m i d mid mid；
• ??2.b）目標值 大于 陣列元素，則代表目標值應該出現在區間 [ m i d + 1 , r ] [mid+1, r] [mid+1,r]，迭代左區間端點： l = m i d + 1 l = mid + 1 l=mid+1；
• ??2.c）目標值 小于 陣列元素，則代表目標值應該出現在區間 [ l , m i d ? 1 ] [l, mid-1] [l,mid?1]，迭代右區間端點： r = m i d ? 1 r = mid - 1 r=mid?1；
• 3）如果這時候 l > r l > r l>r，則說明沒有找到目標值，回傳 ? 1 -1 ?1；否則，回到 2）繼續迭代，

b. 時間復雜度

• 由于每次都是將區間折半，所以二分查找的時間復雜度為 O ( l o g 2 n ) O(log_2n) O(log2?n)，

c. 代碼詳解

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;      // (1)
        while(l <= r) {                      // (2)
            int mid = (l + r) >> 1;          // (3)
            if(nums[mid] == target) {   
                return mid;                  // (4)
            }else if(target > nums[mid]) {
                l = mid + 1;                 // (5)
            }else if(target < nums[mid]) {
                r = mid - 1;                 // (6)
            }
        }
        return -1;                           // (7)
    }
};

• ( 1 ) (1) (1) 由于vector的下標和陣列一樣是從 0 開始的，所以初始的左右查找區間端點為 0 和 陣列長度減一，nums.size()回傳的是陣列的長度；
• ( 2 ) (2) (2) 一直迭代左右區間的端點，直到 左端點 大于 右端點 結束；
• ( 3 ) (3) (3) >> 1等價于除 2，也就是這里mid代表的是l和r的中點；
• ( 4 ) (4) (4) nums[mid] == target表示正好找到了這個數，則直接回傳下標mid；
• ( 5 ) (5) (5) target > nums[mid]表示target這個數在區間 [ m i d + 1 , r ] [mid+1, r] [mid+1,r] 中，所以才有左區間賦值如下：l = mid + 1;
• ( 6 ) (6) (6) target < nums[mid]表示target這個數在區間 [ l , m i d ? 1 ] [l, mid - 1] [l,mid?1] 中，所以才有右區間賦值如下：r = mid - 1;
• ( 7 ) (7) (7) 這一步呼應了 ( 2 ) (2) (2)，表示這不到給定的數，直接回傳 -1；

---

🥢5、雙指標

• 接下來，以一個非常經典的面試題【最長不重復子串】為例，展開對雙指標演算法的講解，

【例題5】給定一個長度為 n ( 1 ≤ n ≤ 1 0 7 ) n (1 \le n \le 10^7) n(1≤n≤107) 的字串 s s s，求一個最長的滿足所有字符不重復的子串，

a. 初步分析

• 首先我們分析一下這個問題的關鍵詞，主要有以下幾個：
• 1） n ≤ 1 0 7 n \le 10^7 n≤107；
• 2）最長；
• 3）所有字符不重復；
• 4）子串；
• 根據以上的幾個關鍵詞，我們可以得出一些結論，首先，根據 n n n 的范圍已經能夠大致確認這是一個需要 O ( n ) O(n) O(n) 或者 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n) 的演算法才能解決的問題；其次，“最長” 這個詞告訴我們，可能是一個動態規劃問題或者貪心問題，也有可能是搜索，所以這個關鍵詞給我們的資訊用處不大；而判斷字符是否重復可以用 哈希表 在 O ( 1 ) O(1) O(1) 的時間內判斷；最后，列舉所有 “子串” 的時間復雜度是 O ( n 2 ) O(n^2) O(n2) 的，

b. 樸素演算法

• 由以上分析，我們可以發現第（1）個 和 第（4）個關鍵詞給我們得出的結論是矛盾的，那么，我們可以先嘗試減小 n n n 的范圍，如果 n ≤ 1000 n \le 1000 n≤1000 時，怎么解決這個問題呢？
• 因為最后求的是滿足條件的最長子串，所以我們如果能夠列舉所有子串，那么選擇長度最長的滿足條件的子串就是答案了（這里的條件是指子串中所有字符都不同），

用 a n s ans ans 記錄我們需要求的最大不重復子串的長度，用一個哈希表 h h h 來代表某個字符是否出現過，演算法描述如下：
??1）列舉子串的左端點 i = 0 → n ? 1 i = 0 \to n-1 i=0→n?1；
??2）清空哈希表 h h h；
??3）列舉子串的右端點 j = i → n ? 1 j = i \to n-1 j=i→n?1，如果當前這個字符 s j s_j sj? 出現過（即 h [ s j ] = t r u e h[s_j] = true h[sj?]=true），則跳出 j j j 的回圈；否則，令 h [ s j ] = t r u e h[s_j] = true h[sj?]=true，并且用當前長度去更新 a n s ans ans（即 a n s = m a x ( a n s , j ? i + 1 ) ans= max(ans, j - i +1) ans=max(ans,j?i+1)）；
??4）回到 2）；

• c++ 代碼實作如下：

int getmaxlen(int n, char *str, int& l, int& r) {
    int ans = 0, i, j, len;
    memset(h, 0, sizeof(h));
    for(i = 0; i < n; ++i) {                // 1)
        j = i;
        memset(h, false, sizeof(h));        // 2)
        while(j < n && !h[str[j]]) {
            h[ str[j] ] = true;             // 3)
            len = j - i + 1;
            if(len > ans)
                ans = len, l = i, r = j;
            ++j;
        }
    }
    return ans;
}

• 1）這一步列舉對應子串的左端點 i i i；
• 2）這一步用于清空哈希表 h h h，其中 h [ s j ] = t r u e h[ s_j ] = true h[sj?]=true 代表原字串的第 j j j 個字符 s j s_j sj? 是否出現在以第 i i i 個字符為左端點的子串中；
• 3）而第三步可以這么理解：如果字串 s [ i : j ] s[i:j] s[i:j] 中已經出現重復的字符，那么 s [ i : j + 1 ] ， s [ i : j + 2 ] , . . . , s [ i : n ? 1 ] s[i:j+1]，s[i:j+2], ... , s[i:n-1] s[i:j+1]，s[i:j+2],...,s[i:n?1] 必然會有重復字符，所以這里不需要繼續往下列舉，直接跳出第二層回圈即可，
• 這個演算法執行完畢， a n s ans ans 就是我們要求的最長不重復子串的長度， [ l , r ] [l, r] [l,r] 代表了最長不重復子串在原字串的區間，正確性毋庸置疑，因為已經列舉了所有子串的情況，如果字符集的個數 z z z，演算法的時間復雜度就是 O ( n z ) O(nz) O(nz)，
• 最后奉上一張動圖，代表了上述樸素演算法的求解程序，如圖所示：
  
• 字串下標從 0 開始，最長無重復子串為： s [ 1 : 5 ] = b c a e d s[1:5] = bcaed s[1:5]=bcaed，長度為 5，
• 由于是字串，字符集的個數 z z z 最多 256，所以時間復雜度基本就是 O ( 256 n ) O(256n) O(256n)，當 n ≤ 1 0 7 n \le 10^7 n≤107 時，這個時間復雜度是無法接受的，需要想辦法優化，

c. 優化演算法

• 如果仔細思考上面樸素演算法的求解程序，就會發現：列舉子串的時候有很多區間是重疊的，所以必然存在許多沒有必要的重復計算，
• 我們考慮一個子串以 s i s_i si? 為左端點， s j s_j sj? 為右端點，且 s [ i : j ? 1 ] s[i:j-1] s[i:j?1] 中不存在重復字符， s [ i : j ] s[i:j] s[i:j] 中存在重復字符（換言之， s j s_j sj? 和 s [ i : j ? 1 ] s[i:j-1] s[i:j?1] 中某個字符相同），如圖所示：
  
• 那么我們沒必要再去檢測 s [ i : j + 1 ] s[i:j+1] s[i:j+1]， s [ i : j + 2 ] s[i:j+2] s[i:j+2]， s [ i : n ? 1 ] s[i:n-1] s[i:n?1] 這幾個字串的合法性，因為當前情況 s [ i : j ] s[i:j] s[i:j] 是非法的，而這些字串是完全包含 s [ i : j ] s[i:j] s[i:j] 的，所以它們必然也是不合法的，
• 那么我們可以把列舉的左端點自增，即： i = i + 1 i = i +1 i=i+1，這時，按照樸素演算法的實作，右端點需要重置，即 j = i j = i j=i，實際上這里的右端點可以不動，
• 可以這么考慮，由于 s j s_j sj? 這個字符和 s [ i : j ? 1 ] s[i:j-1] s[i:j?1] 中的字符產生了重復，假設這個重復的字符的下標為 k k k，那么 i i i 必須滿足 i > k i \gt k i>k，換言之， i i i 可以一直自增，直到 i = k + 1 i = k+1 i=k+1，如圖所示：
  
• 利用上述思路，我們重新實作 最長不重復子串 的演算法， c++ 代碼實作如下：

int getmaxlen(int n, char *str, int& l, int& r) {
    int ans = 0, i = 0, j = -1, len;   // 1)
    memset(h, 0, sizeof(h));           // 2)
    while (j++ < n - 1) {              // 3)
        ++h[ str[j] ];                 // 4)
        while (h[ str[j] ] > 1) {      // 5)
            --h[ str[i] ];
            ++i;
        }
        len = j - i + 1;              
        if(len > ans)                  // 6)
            ans = len, l = i, r = j;
    }
    return ans;
}

• 1）初始化 i = 0, j = -1，代表 s [ i : j ] s[i:j] s[i:j] 為一個空串，從空串開始列舉；
• 2）同樣需要維護一個哈希表，哈希表記錄的是當前列舉的區間 s [ i : j ] s[i:j] s[i:j] 中每個字符的個數；
• 3）只推進子串的右端點；
• 4）在哈希表中記錄字符的個數；
• 5）當 h[ str[j] ] > 1滿足時，代表出現了重復字符，這時候左端點 i i i 推進，直到沒有重復字符為止；
• 6）記錄當前最優解 j-i+1；
• 這個演算法執行完畢，我們就可以得到最長不重復子串的長度為 a n s ans ans，并且 i i i 和 j j j 這兩個指標分別只自增 n n n 次，兩者自增相互獨立，是一個相加而非相乘的關系，所以這個演算法的時間復雜度為 O ( n ) O(n) O(n) ，
• 利用該優化演算法優化后的最長不重復子串的求解程序如圖所示：
  
• 參考這個圖，一個比較通俗易懂的解釋：當區間 [ i , j ] [i, j] [i,j] 中存在重復（紅色）字符時，左指標 i i i 自增；否則，右指標 j j j 自增，

---

🍴6、差分法

• 差分法一般配合前綴和，
• 對于區間 [ l , r ] [l, r] [l,r] 內求滿足數量的數，可以利用差分法分解問題；
• 假設 [ 0 , x ] [0, x] [0,x] 內的 g o o d n u m b e r good \ number good number 數量為 g x g_x gx?，那么區間 [ l , r ] [l, r] [l,r] 內的數量就是 g r ? g l ? 1 g_r - g_{l-1} gr??gl?1?；分別用同樣的方法求出 g r g_r gr? 和 g l ? 1 g_{l-1} gl?1?，再相減即可；
  

🅱7、位運算

• 位運算可以理解成對二進制數字上的每一個位進行操作的運算，
• 位運算分為 布爾位運算子 和 移位位運算子，
• 布爾位運算子又分為 位與(&)、位或(|)、異或(^)、按位取反(~)；移位位運算子分為 左移(<<) 和 右移(>>)，
• 如圖所示：
  
• 位運算的特點是陳述句短，但是可以干大事！

a、位與

??【例題7】給出一個整數，現在要求將這個整數轉換成二進制以后，將末尾連續的1都變成0，輸出改變后的數（以十進制輸出即可），

• 我們知道，這個數的二進制表示形式一定是：
• . . . 0 11...11 ? k ...0\underbrace{11...11}_{\rm k} ...0k 11...11??
• 如果，我們把這個二進制數加上1，得到的就是：
• . . . 1 00...00 ? k ...1\underbrace{00...00}_{\rm k} ...1k 00...00??
• 我們把這兩個數進行位與運算，得到：
• . . . 0 00...00 ? k ...0\underbrace{00...00}_{\rm k} ...0k 00...00??
• 所以，你學會了嗎？代碼如下：

x &= x - 1;

b、位或

【例題8】給定一個整數 x x x，將它低位連續的 0 都變成 1，

• 假設這個整數低位連續有 k k k 個零，二進制表示如下：
• . . . 1 00...00 ? k ...1\underbrace{00...00}_{\rm k} ...1k 00...00??
• 那么，如果我們對它進行減一操作，得到的二進制數就是：
• . . . 0 11...11 ? k ...0\underbrace{11...11}_{\rm k} ...0k 11...11??
• 我們發現，只要對這兩個數進行位或，就能得到：
• . . . 1 11...11 ? k ...1\underbrace{11...11}_{\rm k} ...1k 11...11??
• 也正是題目所求，所以代碼實作如下：

#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x | (x-1) );    // (1)
    return 0;
}

• ( 1 ) (1) (1) x | (x-1)就是題目所求的 “低位連續零變一” ，

c、異或

【例題9】給定兩個數 a a a 和 b b b，用異或運算交換它們的值，

• 這個是比較老的面試題了，直接給出代碼：

#include <stdio.h>
int main() {
    int a, b;
	while (scanf("%d %d", &a, &b) != EOF) {
	    a = a ^ b;   // (1)
	    b = a ^ b;   // (2)
	    a = a ^ b;   // (3)
	    printf("%d %d\n", a, b);
	}
	return 0;
}

• 我們直接來看 ( 1 ) (1) (1) 和 ( 2 ) (2) (2) 這兩句話，相當于b等于a ^ b ^ b，根據異或的幾個性質，我們知道，這時候的b的值已經變成原先a的值了，
• 而再來看第 ( 3 ) (3) (3) 句話，相當于a等于a ^ b ^ a，還是根據異或的幾個性質，這時候，a的值已經變成了原先b的值，
• 從而實作了變數a和b的交換，

d、左移

• 對于 x x x 模上一個 2 的次冪的數 y y y，我們可以轉換成位與上 2 y ? 1 2^y-1 2y?1，
• 即在數學上的：
• x m o d 2 y x \ mod \ 2^y x mod 2y
• 在計算機中就可以用一行代碼表示：x & ((1 << y) - 1)，

---

🧡8、貪心

• 貪心，一般就是按照當前最優解，去推算全域最優解，
• 所以，只有當當前最優解和全域最優解一致時才能用貪心演算法，貪心演算法的證明是比較難的，但是一些簡單的貪心問題會比較直觀，很容易看出來這個能夠這么貪，

?9、遞回分治

• 分治，就是把問題分成若干子問題求解，子問題解決后，問題就解決了，一般利用遞回實作，屬于初學者比較頭疼的內容，遞回一開始學習的時候，一定要注意全域變數和區域變數的關系，

🙉飯不食，水不飲，題必須刷🙉
還不會C語言，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？上簡單題！ 🧡《C語言入門100例》🧡
LeetCode 太簡單？大神盤他！ 🌌《夜深人靜寫演算法》🌌

LeetCode 46. 全排列

?【例題10】給定一個 不含重復數字 的長度小于 7 的陣列 n u m s nums nums ，回傳其 所有可能的全排列，
??樣例輸入： n u m s = [ 1 , 2 , 3 ] nums = [1,2,3] nums=[1,2,3]
??樣例輸出： [ [ 1 , 2 , 3 ] , [ 1 , 3 , 2 ] , [ 2 , 1 , 3 ] , [ 2 , 3 , 1 ] , [ 3 , 1 , 2 ] , [ 3 , 2 , 1 ] ] [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

a. 思路分析

• 全排列的種數是 n ! n! n!，這是最典型的深搜問題，我們可以把 n n n 個數兩兩建立無向邊（即任意兩個結點之間都有邊，也就是一個 n n n 個結點的完全圖），然后對每個點作為起點，分別做一次深度優先搜索，當所有點都已經標記時，輸出當前的搜索路徑，就是其中一個排列；
• 這里需要注意的是，回溯的時候需要將原先標記的點的標記取消，否則只能輸出一個排列，
• 如下圖，代表的是3個數的圖表示：
  
• 3個數的全排列的深度優先搜索空間樹如下圖所示：
  
• 關于深度優先搜索的更深入內容，可以參考這篇文章：夜深人靜寫演算法（一）- 搜索入門，

b. 時間復雜度

• 由于每次訪問后會將標記過的節點標記回來，所以時間復雜度就是排列數，即 O ( n ! ) O(n!) O(n!)，

c. 代碼詳解

class Solution {
    int hash[6];

    void dfs(int dep, int maxdep, vector<int>& nums, vector<vector<int>>& ans, vector<int>& st) {                                                            // (1)
        if(dep == maxdep) {
            ans.push_back( st );                             // (2)
            return ;
        }

        for(int i = 0; i < maxdep; ++i) {                    
            if(!hash[i]) {                                   // (3)
                hash[i] = 1;                                
                st.push_back(  nums[i] );                   
                dfs(dep + 1, maxdep, nums, ans, st);         // (4)
                st.pop_back();                               // (5)
                hash[i] = 0;                                 // (6)
            }
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;            
        memset(hash, 0, sizeof(hash));        
        vector<int> st; 
        dfs(0, nums.size(), nums, ans, st);     
        return ans;
    }
};

• ( 1 ) (1) (1) dep代表本地遞回訪問第幾個節點，maxdep代表遞回的層數，vector<int>& nums則代表原始輸入陣列，vector<vector<int>>& ans代表結果陣列，vector<int>& st代表存盤當前搜索結果的堆疊；
• ( 2 ) (2) (2) dep == maxdep代表一次全排列訪問，這時候得到一個可行解，放入結果陣列中；
• ( 3 ) (3) (3) 如果節點 i i i 未訪問，則將第 i i i 個節點的值塞入搜索結果堆疊，并且用hash陣列標記已訪問；
• ( 4 ) (4) (4) 繼續遞回呼叫下一層；
• ( 5 ) (5) (5) 將堆疊頂元素彈出，代表本次訪問的回溯；
• ( 6 ) (6) (6) 取消陣列標記；

---

🚊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、入門演算法

種類	鏈接
演算法	演算法入門
資料結構	資料結構入門
陣列字串專題	陣列和字串
動態規劃專題	動態規劃入門、DP路徑問題

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

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

種類	鏈接
演算法	初級演算法
堆疊和佇列專題	佇列 & 堆疊

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

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

種類	鏈接
演算法	中極演算法
二叉樹專題	二叉樹
熱門題	熱門題 TOP 100

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

🚍1、進階動態規劃

文章鏈接	難度等級	推薦閱讀
夜深人靜寫演算法（二）- 動態規劃入門	★☆☆☆☆	★★★★★
夜深人靜寫演算法（二十六）- 記憶化搜索	★☆☆☆☆	★★★★★
夜深人靜寫演算法（十九）- 背包總覽	★☆☆☆☆	★★★★★
夜深人靜寫演算法（二十）- 最長單調子序列	★☆☆☆☆	★★★★★
夜深人靜寫演算法（二十一）- 最長公共子序列	★☆☆☆☆	★★★★★
夜深人靜寫演算法（二十二）- 最小編輯距離	★★☆☆☆	★★★★☆
夜深人靜寫演算法（十四）- 0/1 背包	★☆☆☆☆	★★★★☆
夜深人靜寫演算法（十五）- 完全背包	★★☆☆☆	★★★★☆
夜深人靜寫演算法（十六）- 多重背包	★★☆☆☆	★★★★☆
夜深人靜寫演算法（二十七）- 區間DP	★★★☆☆	★★★★☆
夜深人靜寫演算法（二十九）- 數位DP	★★★☆☆	★★★★★
夜深人靜寫演算法（十七）- 分組背包	★★★☆☆	★★★☆☆
夜深人靜寫演算法（十八）- 依賴背包	★★★★☆	★★☆☆☆
夜深人靜寫演算法（六）- RMQ	★★★☆☆	★★☆☆☆
樹形DP	待更新	…
組合博弈	待更新	…
組合計數DP	待更新	…
四邊形不等式	待更新	…
狀態壓縮DP/TSP	待更新	…
斜率優化的動態規劃	待更新	…
插頭DP	待更新	…

🪐2、強勁圖論搜索

1、深度優先搜索

文章鏈接	難度等級	推薦閱讀
夜深人靜寫演算法（一）- 搜索入門	★☆☆☆☆	★★★☆☆
夜深人靜寫演算法（八）- 二分圖最大匹配	★★☆☆☆	★★☆☆☆
最大團	待更新	…
最小生成樹	待更新	…
樹的分治	待更新	…
迭代加深 IDA*	待更新	…
有向圖強連通分量和2-sat	待更新	…
無向圖割邊割點	待更新	…
帶權圖的二分圖匹配	待更新	…
哈密爾頓回路	待更新	…
最近公共祖先	待更新	…
歐拉回路圈套圈	待更新	…
最小費用最大流	待更新	…
最小樹形圖	待更新	…

2、廣度優先搜索

文章鏈接	難度等級	推薦閱讀
夜深人靜寫演算法（十）- 單向廣搜	★★☆☆☆	★★★★☆
夜深人靜寫演算法（二十三）- 最短路	★★★☆☆	★★★★☆
夜深人靜寫演算法（二十五）- 穩定婚姻	★★☆☆☆	★★☆☆☆
夜深人靜寫演算法（二十四）- 最短路徑樹	★★★☆☆	★☆☆☆☆
K 短路	待更新	…
差分約束	待更新	…
拓撲排序	待更新	…
A*	待更新	…
雙向廣搜	待更新	…
最大流 最小割	待更新	…

0??3、進階初等數論

文章鏈接	難度等級	推薦閱讀
夜深人靜寫演算法（三）- 初等數論入門	★★☆☆☆	★★★★☆
夜深人靜寫演算法（三十）- 二分快速冪	★☆☆☆☆	★★★★★
夜深人靜寫演算法（三十一）- 歐拉函式	★★★☆☆	★★★★★
夜深人靜寫演算法（三十二）- 費馬小定理	★★☆☆☆	★★★☆☆
夜深人靜寫演算法（三十三）- 擴展歐拉定理	★★★☆☆	★★★★☆
夜深人靜寫演算法（三十四）- 逆元	★★★☆☆	★★★★☆
夜深人靜寫演算法（三十五）- RSA 加密解密	★★★☆☆	★★★★★
夜深人靜寫演算法（三十六）- 中國剩余定理	★★☆☆☆	★★★☆☆
夜深人靜寫演算法（三十七）- 威爾遜定理	★★☆☆☆	★★★☆☆
夜深人靜寫演算法（三十八）- 整數分塊	★★☆☆☆	★★★★☆
盧卡斯定理	待更新	…
狄利克雷卷積	待更新	…
莫比烏斯反演	待更新	…
容斥原理	待更新	…
拉賓米勒	待更新	…
Pollard rho	待更新	…
莫隊	待更新	…
原根	待更新	…
大步小步演算法	待更新	…
二次剩余	待更新	…
矩陣二分快速冪	待更新	…
Polya環形計數	待更新	…

🛑4、進階計算幾何

📏5、字串的匹配

🎄6、高級資料結構

---

🙉飯不食，水不飲，題必須刷🙉
還不會C語言，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？上簡單題！ 🧡《C語言入門100例》🧡
LeetCode 太簡單？大神盤他！ 🌌《夜深人靜寫演算法》🌌

---