前言

??「 資料結構 」 和 「 演算法 」 是密不可分的，兩者往往是「 相輔相成 」的存在，所以，在學習 「 資料結構 」 的程序中，不免會遇到各種「 演算法 」，
??到底是先學 資料結構 ，還是先學 演算法，我認為不必糾結這個問題，一定是一起學的，
??資料結構 常用的操作一般為：「 增 」「 刪 」「 改 」「 查 」，基本上所有的資料結構都是圍繞這幾個操作進行展開的，
??那么這篇文章，作者將主要來聊聊：

「 演算法和資料結構 」

直接跳到末尾 獲取粉絲專屬福利

<iframe id="5OPDwdlY-1639950019877" src="https://player.bilibili.com/player.html?aid=764932417" allowfullscreen="true" data-mediaembed="bilibili"></iframe>

LeetCode演算法學習路線

完整版視頻地址

專欄	定位	適宜人群
「 光天化日學C語言 」	「 入門 」	沒有任何語言基礎
「 LeetCode零基礎指南 」	「 初級 」	零基礎快速上手力扣
「 C語言入門100例 」	「 中級 」	零基礎持續C語言練習教程
「 演算法零基礎100講 」	「 高級 」	零基礎持續演算法練習教程
「 畫解資料結構 」	「 高級 」	「 推薦 」 資料結構動圖教程
「 演算法進階50講 」	「 資深 」	進階持續演算法練習教程
「 LeetCode演算法題集匯總 」	「 資深 」	全面的力扣演算法題練習集錦
「 夜深人靜寫演算法 」	「 資級 」	競賽高端演算法集錦

??在學習資料結構的程序中，如果你能夠自己把圖畫出來，并且能夠描述整個 「 增 」「 刪 」「 改 」「 查 」 的程序，那么說明你已經真正理解了資料結構的真諦，來看下下面幾張圖：

一、演算法和資料結構的重要性

1、為什么要學習演算法

??如果你只是想學會寫代碼，或許 「 演算法與資料結構 」 并不是那么重要，但是，想要進一步發展自己的事業，「 演算法與資料結構 」 是必不可少的，
??現在一些主流的大廠，諸如：位元組、網易、騰訊、阿里、美團、京東、滴滴 等等，在面時都會讓候選人寫一道 「 演算法題 」 ，如果你敲不出來，可能你的 offer 年包就打了骨折，或者直接與 offer 失之交臂，都是有可能的，
??當然，它不能完全代表你的編碼能力（因為有些演算法確實是很巧妙，加上緊張的面試氛圍，想不出來其實也是正常的），但是你能確保面試官是這么想的嗎？我們要做的是十足的準備，既然決定出來，offer 當然是越高越好，畢竟大家都要養家糊口，房價又這么貴，如果能夠在演算法這一塊取得先機，也不失為一個捷徑，
??所以，你問我演算法和資料結構有什么用？我可以很明確的說，和你的年薪息息相關，當然，面試中 「演算法與資料結構」 知識的考察只是面試內容的一部分，其它還有很多面試要考察的內容，當然不是本文主要核心內容，這里就不做展開了，

2、如何有效的學習

??這篇文章中，我會著重講解一些常見的 「 演算法和資料結構 」 的設計思想，并且配上動圖，主要針對面試中常見的問題和新手朋友們比較難理解的點進行決議，當然，后面也會給出面向演算法競賽的提綱，如果有興趣深入學習的歡迎在評論區留言，一起成長交流，
??零基礎學演算法的最好方法，莫過于 「 刷題 」 了，任何事情都是需要 「 堅持 」 的，刷題也一樣，沒有刷夠足夠的題，就很難做出系統性的總結，所以上大學的時候，我花了三年的時間來刷題， 作業以后還是會抽點時間出來刷題，
??當然，每天不需要花太多時間在這個上面，把這個事情做成一個 「 規劃 」 ，按照長期去推進，反正也沒有 KPI 壓力，就當成是作業之余的一種消遣，還能夠提升思維能力，所謂： 「 十年磨一劍，今朝把示君 」 ，

3、堅持并且把它當成興趣

??相信看我文章的大多數都是「 大學生 」，能上大學的都是「 精英 」，那么我們自然要「 精益求精 」，如果你還是「 大一 」，那么太好了，你擁有大把時間，當然你可以選擇「 刷劇 」，然而，「 學好演算法 」，三年后的你自然「 不能同日而語 」，
??如果你滿足如下：
?? ( 1 ) (1) (1) 有強烈欲望「 想要學好C語言 」的人
?? ( 2 ) (2) (2) 有強烈欲望「 想要學好C++ 」的人
?? ( 3 ) (3) (3) 有強烈欲望「 想要學好資料結構 」的人
?? ( 4 ) (4) (4) 有強烈欲望「 想學好演算法 」的人
?? ( 5 ) (5) (5) 有強烈欲望「 想進大廠 」的人
??如果你滿足以上任意一點，那么，我們就是志同道合的人啦！
??🔥聯系作者，或者掃作者主頁二維碼加群，加入我們吧🔥

4、首先要有語言基礎

??單純學習語言未免太過枯燥乏味，所以建議一邊學習一遍刷題，養成每天刷題的習慣，在刷題的程序中鞏固語法，每過一個題相當于是一次正反饋，能夠讓你在刷題旅途中酣暢淋漓，從而更好的保證你一直堅持下去，在沒有任何演算法基礎的情況下，可以按照我提供的專欄來刷題，這也是上上個視頻提到的 九日集訓 的完整教材，主要有以下幾個內容：

??這個專欄主要講解了一些 LeetCode 刷題時的一些難點和要點，主要分為以下幾個章節，并且會持續補充一些方法論的文章，文章有試讀，可以簡單先看一看試讀文章，

🍠《LeetCode零基礎指南》🍠
導讀 （第一講）函式 （第二講）回圈 （第三講）陣列 （第四講）指標 （第五講）排序 （第六講）貪心 （第七講）矩陣 （第八講）二級指標 （第九講）簡單遞回

5、九日集訓

??「 九日集訓 」是博主推出的一個能夠白嫖付費專欄「 LeetCode零基礎指南 」的活動，通過 「 專欄中的聯系方式 」 或者 「 本文末尾的聯系方式 」 聯系博主，進行報名即可參加，九日一個回圈，第二期計劃 「 2021.12.02 」 開啟，

??玩法很簡單，每天會開啟一篇試讀文章，要求有三點：
??1）閱讀完文章后，課后習題 「 全部刷完 」（都能在文中找到解法，需要自己敲一遍代碼）；
??2）寫 「 學習報告 」 并發布社區 九日集訓(每日打卡) 頻道
??3）在 「 打卡帖 」 提交 「 學習報告 」 鏈接；

??完成以上三點后方可晉級到下一天，所有堅持到 9天 的同學，會成為 「 英雄演算法聯盟合伙人 」 群成員，只限500個名額，優勝劣汰，和精英在一起，無論是溝通，學習，都能有更好的發展，你接觸到的人脈也都是不一樣的，等找作業的時候，我也會為大家打通 hr 和獵頭，讓你前程無憂～
??詳細規則參見：九日集訓規則詳解，
??目前第四輪「 九日集訓 」已經進行到第四天，即將開啟第五輪，

6、零基礎如何學習演算法

??數學是演算法的基石，可以先從刷數學題開始，
??LeetCode上的題目相比ACM來說，數學題較少，所以對數學有恐懼的同學也不必擔心，比較常見的數學題主要有：位運算，線性代數，計算幾何，組合數學 ，數論，概率論，

板塊	題數
位運算	30
線性代數	20
計算幾何	5
組合數學	5
數論	5
概率論	5

1）位運算

??位運算主要有：位與、位或、按位取反、異或、左移 和 右移，對應的文章可以看：

(第42講) 位運算 (位與) 入門 (第44講) 位運算 (位或) 入門 (第46講) 位運算 (異或) 入門 (第48講) 位運算 (左移) 入門 (第49講) 位運算 (右移) 入門 (第50講) 位運算 (取反) 入門

??位運算是計算機的精華所在，是必須掌握的內容，大概每個運算操作刷 三 到 五 題就基本有感覺了，

2）線性代數

??線性代數在刷題中，主要內容有 矩陣運算 和 高斯消元，矩陣在程式中的抽象就是二維陣列，如下：

（第七講）矩陣

??高斯消元是求解多元一次方程組的，一般在競賽中會遇到，面試一般不問，因為面試官可能也不會，

夜深人靜寫演算法 (十六) 高斯消元

3）計算幾何

??數論 是 ACM 中一個比較重要的內容，至少一旦出現，一定不會是一個水題，編碼量較大，但是在 LeetCode 中題型較少，可以適當掌握一些基礎內容即可，對應文章如下：

夜深人靜寫演算法 （四）- 計算幾何入門 夜夜深人靜寫演算法（十二）- 凸包

4）數論

??數論 是 ACM 中一個比較重要的內容，但是在 LeetCode 中題型較少，可以適當掌握一些基礎內容即可，對應文章如下：

夜深人靜寫演算法 (三) 初等數論入門

5）組合數學 和 概率論

??組合數學 和 概率論，在 LeetCode 中題目較少，有興趣可以刷一刷，沒有興趣就不要去刷了，畢竟興趣才是最好的老師，對應的文章如下：

(第4講) 組合數 (第30講) 概率問題

7、零基礎如何學習資料結構

??學習資料結構之前，選擇一款相對來說心儀的教程是必不可少的，我這里準備了一個用影片來解釋資料結構的教程，在我這也有，就是：

🌳《畫解資料結構》🌳
??這是我目前來說，寫的最用心的一個教程，里面匯集了大量的動圖，目前更新已經過半，好評如潮，
??當然，一邊學習，一邊做一些練習題是必不可少的，接下來就是推薦一個我自己整理的題集了，這個題集匯集了大量的演算法，可以幫你在前行的路上掃平不少障礙， 🌌《演算法入門指引》🌌
??在看上述題目時，如果遇到難以解決的問題，可以參考如下解題報告專欄： 🌌《演算法解題報告》🌌

8、資料結構和演算法是相輔相成的

??如果你在刷題的程序中，已經愛上了演算法，那么恭喜你，你將會無法自拔，一直刷題一直爽，在遇到一些高端的演算法時，也不要驚慌，這里推薦一個競賽選手金典圖文教程，如下：

💜《夜深人靜寫演算法》💜

二、資料結構是根基

??學習演算法，資料結構是根基，沒有一些資料結構做支撐，這個演算法都沒有落腳點，任何一個簡單的演算法都是需要資料結構來支撐的，比如最簡單的演算法，

1、陣列

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

一、概念

1、順序存盤

??順序存盤結構，是指用一段地址連續的存盤單元依次存盤線性表的資料元素，

2、存盤方式

??在編程語言中，用一維陣列來實作順序存盤結構，在C語言中，把第一個資料元素存盤到下標為 0 的位置中，把第 2 個資料元素存盤到下標為 1 的位置中，以此類推，

3、長度和容量

??陣列的長度指的是陣列當前有多少個元素，陣列的容量指的是陣列最大能夠存放多少個元素，如果陣列元素大于最大能存盤的范圍，在程式上是不允許的，可能會產生意想不到的問題，實作上是需要規避的，

??如上圖所示，陣列的長度為 5，即紅色部分；容量為 8，即紅色 加 藍色部分，

4、資料結構定義

#define MAXN 1024
#define DataType int        // (1)

struct SeqList {
    DataType data[MAXN];    // (2)
    int length;             // (3)
}; 

• ( 1 ) (1) (1) 陣列型別為DataType，定義為int；
• ( 2 ) (2) (2) SeqList定義的就是一個最多存放MAXN個元素的陣列，MAXN代表陣列容量；
• ( 3 ) (3) (3) length代表陣列長度，即當前的元素個數，

二、常用介面實作

1、索引

??索引 就是通過 陣列下標 尋找 陣列元素 的程序，C語言實作如下：

DataType SeqListIndex(struct SeqList *sq, int i) {
    return sq->data[i];          // (1)
}

• ( 1 ) (1) (1) 呼叫方需要注意 i i i 的取值必須為非負整數，且小于陣列最大長度，否則有可能導致例外，引發崩潰，
• 索引的演算法時間復雜度為 O ( 1 ) O(1) O(1)，
  

2、查找

??查找 就是通過 陣列元素 尋找 陣列下標 的程序，是索引的逆程序，
??對于有序陣列，可以采用 二分 進行查找，時間復雜度為 O ( l o g 2 n ) O(log_2n) O(log2?n)；對于無序陣列，只能通過遍歷比較，由于元素可能不在陣列中，可能遍歷全表，所以查找的最壞時間復雜度為 O ( n ) O(n) O(n)，
??簡單介紹一個線性查找的例子，實作如下：

DataType SeqListFind(struct SeqList *sq, DataType dt) {
    int i;
    for(i = 0; i < sq->length; ++i) { // (1)
        if(sq->data[i] == dt) {
            return i;                 // (2)
        }    
    }
    return -1;                        // (3)
}

• ( 1 ) (1) (1) 遍歷陣列元素；
• ( 2 ) (2) (2) 對陣列元素 和 傳入的資料進行判等，一旦發現相等就回傳對應資料的下標；
• ( 3 ) (3) (3) 當陣列遍歷完還是找不到，說明這個資料肯定是不存在的，直接回傳 ? 1 -1 ?1，
  

3、獲取長度

??獲取 陣列的長度 指的是查詢當前有多少元素，可以直接用結構體的內部變數，C語言代碼實作如下：

DataType SeqListGetLength(struct SeqList *sq) {
    return sq->length; 
}

4、插入

??插入介面定義為：在陣列的第 k k k 個元素前插入一個數 v v v，由于陣列是連續存盤的，那么從 k k k 個元素往后的元素都必須往后移動一位，當 k = 0 k=0 k=0 時，所有元素都必須移動，所以最壞時間復雜度為 O ( n ) O(n) O(n)，C語言代碼實作如下：

int SeqListInsert(struct SeqList *sq, int k, DataType v) {
    int i;
    if(sq->length == MAXN) {
        return 0;                        // (1) 
    } 
    for(i = sq->length; i > k; --i) {
        sq->data[i] = sq->data[i-1];     // (2) 
    }
    sq->data[k] = v;                     // (3) 
    sq->length ++;                       // (4) 
    return 1;                            // (5) 
}

• ( 1 ) (1) (1) 當元素個數已滿時，回傳 0 0 0 代表插入失敗；
• ( 2 ) (2) (2) 從第 k k k 個數開始，每個數往后移動一個位置，注意必須逆序；
• ( 3 ) (3) (3) 將第 k k k 個數變成 v v v；
• ( 4 ) (4) (4) 插入了一個數，陣列長度加一；
• ( 5 ) (5) (5) 回傳 1 1 1 代表插入成功；

5、洗掉

??插入介面定義為：將陣列的第 k k k 個元素洗掉，由于陣列是連續存盤的，那么第 k k k 個元素洗掉，往后的元素勢必要往前移動一位，當 k = 0 k=0 k=0 時，所有元素都必須移動，所以最壞時間復雜度為 O ( n ) O(n) O(n)，C語言代碼實作如下：

int SeqListDelete(struct SeqList *sq, int k) {
    int i;
    if(sq->length == 0) {
        return 0;                        // (1) 
    } 
    for(i = k; i < sq->length - 1; ++i) {
        sq->data[i] = sq->data[i+1];     // (2) 
    } 
    sq->length --;                       // (3) 
    return 1;                            // (4)  
}

• ( 1 ) (1) (1) 回傳0代表洗掉失敗；
• ( 2 ) (2) (2) 從前往后；
• ( 3 ) (3) (3) 陣列長度減一；
• ( 4 ) (4) (4) 回傳1代表洗掉成功；
• 想要了解更多陣列相關內容，可以參考：《畫解資料結構》（1 - 1）- 陣列，

---

2、鏈表

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

一、概念

• 對于順序存盤的結構，如陣列，最大的缺點就是：插入 和 洗掉 的時候需要移動大量的元素，所以，基于前人的智慧，他們發明了鏈表，

1、鏈表定義

??鏈表 是由一個個 結點 組成，每個 結點 之間通過 鏈接關系 串聯起來，每個 結點 都有一個 后繼節點，最后一個 結點 的 后繼結點 為 空結點，如下圖所示：

• 由鏈接關系A -> B組織起來的兩個結點，B被稱為A的后繼結點，A被稱為B的前驅結點，
• 鏈表 分為 單向鏈表、雙向鏈表、回圈鏈表 等等，本文要介紹的鏈表是 單向鏈表，
• 由于鏈表是由一個個 結點 組成，所以我們先來看下 結點 的實作，

2、結點結構體定義

typedef int DataType;
struct ListNode {
    DataType data;  // (1)
    ListNode *next; // (2)
};

• ( 1 ) (1) (1) 資料域：可以是任意型別，由編碼的人自行指定；這段代碼中，利用typedef將它和int同名，本文的 資料域 也會全部采用int型別進行講解；
• ( 2 ) (2) (2) 指標域：指向 后繼結點 的地址；
• 一個結點包含的兩部分如下圖所示：
  

3、結點的創建

• 我們通過 C語言 中的庫函式malloc來創建一個 鏈表結點，然后對 資料域 和 指標域 進行賦值，代碼實作如下：

ListNode *ListCreateNode(DataType data) {
    ListNode *node = (ListNode *) malloc ( sizeof(ListNode) ); // (1)
    node->data = data;                                         // (2)
    node->next = NULL;                                         // (3)
    return node;                                               // (4)
}

• ( 1 ) (1) (1) 利用系統庫函式malloc分配一塊記憶體空間，用來存放ListNode即鏈表結點物件；
• ( 2 ) (2) (2) 將 資料域 置為函式傳參data；
• ( 3 ) (3) (3) 將 指標域 置空，代表這是一個孤立的 鏈表結點；
• ( 4 ) (4) (4) 回傳這個結點的指標，
• 創建完畢以后，這個孤立結點如下所示：
  

二、鏈表的創建 - 尾插法

• 那么接下來，讓我們看下如何通過一個 陣列中的資料 來創建一個鏈表，

1、演算法描述

??首先介紹 尾插法 ，顧名思義，即 從鏈表尾部插入 的意思，就是記錄一個 鏈表尾結點，然后遍歷給定陣列，將陣列元素一個一個插到鏈表的尾部，每插入一個結點，則將它更新為新的 鏈表尾結點，注意初始情況下，鏈表尾結點 為空，

2、影片演示

上圖演示的是 尾插法 的整個程序，其中：
??head 代表鏈表頭結點，創建完一個結點以后，它就保持不變了；
??tail 代表鏈表尾結點，即動圖中的 綠色結點；
??vtx 代表正在插入鏈表尾部的結點，即動圖中的 橙色結點，插入完畢以后，vtx 變成 tail；

• 看完這個動圖，你應該已經大致理解了 鏈表的創建程序，那么接下來，我們用程式語言來描述一下整個程序，這里采用的是 C語言 的形式，如果你是 Java、C#、Python 技術堆疊的，也可以試著寫出自己的版本，
• 語言并不是關鍵，思維才是關鍵，

3、原始碼詳解

• C語言 實作如下：

ListNode *ListCreateListByTail(int n, int a[]) {
    ListNode *head, *tail, *vtx;         // (1) 
    int idx;                              
    if(n <= 0)
        return NULL;                     // (2) 
    idx = 0;
    vtx = ListCreateNode(a[0]);          // (3) 
    head = tail = vtx;                   // (4)  
    while(++idx < n) {                   // (5) 
        vtx = ListCreateNode(a[idx]);    // (6) 
        tail->next = vtx;                // (7) 
        tail = vtx;                      // (8)  
    } 
    return head;                         // (9) 
} 

對應的注釋如下：
?? ( 1 ) (1) (1) head存盤頭結點的地址，tail存盤尾結點的地址，vtx存盤當前正在插入結點的地址；
?? ( 2 ) (2) (2) 當需要創建的元素個數為 0 時，直接回傳空鏈表；
?? ( 3 ) (3) (3) 創建一個 資料域 為a[0]的鏈表結點；
?? ( 4 ) (4) (4) 由于初始情況下只有一個結點，所以將鏈表頭結點head和鏈表尾結點tail都置為vtx；
?? ( 5 ) (5) (5) 從陣列第 1 個元素 (0 - based) 開始，回圈遍歷陣列；
?? ( 6 ) (6) (6) 由于陣列中第 0 個元素已經創建過了，所以這里只需要對除了第 0 個元素以外的資料創建鏈表結點；
?? ( 7 ) (7) (7) 結點創建出來后，將當前鏈表尾結點tail的 后繼結點 置為vtx；
?? ( 8 ) (8) (8) 將最近創建的結點vtx作為新的 鏈表尾結點；
?? ( 9 ) (9) (9) 回傳鏈表頭結點；

---

• 尾插法 比較符合直觀的思維邏輯，但是就代碼量來說還是有點長（注意：在實作相同功能的情況下，代碼應該是越簡潔，越簡單越好的），
• 于是，我們引入了另一種創建鏈表的方式 —— 頭插法，

三、鏈表的創建 - 頭插法

1、演算法描述

??頭插法，顧名思義，就是每次從頭結點前面進行插入，但是這樣一來，就會導致插入的資料元素是 逆序 的，所以我們需要 逆序訪問陣列 執行插入，此所謂 負負得正 的思想，

• 它的特點是代碼量短，且 常數時間復雜度 低，雖然沒有 尾插法 那么直觀，但是代碼簡潔，更加容易閱讀，

2、影片演示

上圖所示的是 頭插法 的整個插入程序，其中：
??head 代表鏈表頭結點，即動圖中的 綠色結點，每新加一個結點，頭結點就變成了新加入的結點；
??tail 代表鏈表尾結點，創建完一個結點以后，它就保持不變了；
??vtx 代表正在插入鏈表頭部的結點，即動圖中的 橙色結點，插入完畢以后，vtx 變成 head；

3、原始碼詳解

ListNode *ListCreateListByHead(int n, int *a) {
    ListNode *head = NULL, *vtx;       // (1) 
    while(n--) {                       // (2) 
        vtx = ListCreateNode(a[n]);    // (3) 
        vtx->next = head;              // (4) 
        head = vtx;                    // (5) 
    } 
    return head;                       // (6) 
} 

對應的注釋如下：
?? ( 1 ) (1) (1) head存盤頭結點的地址，初始為空鏈表， vtx存盤當前正在插入結點的地址；
?? ( 2 ) (2) (2) 總共需要插入 n n n 個結點，所以采用逆序的 n n n 次回圈；
?? ( 3 ) (3) (3) 創建一個元素值為a[i]的鏈表結點，注意，由于逆序，所以這里 i i i 的取值為 n ? 1 → 0 n-1 \to 0 n?1→0；
?? ( 4 ) (4) (4) 將當前創建的結點的 后繼結點 置為 鏈表的頭結點head；
?? ( 5 ) (5) (5) 將鏈表頭結點head置為vtx；
?? ( 6 ) (6) (6) 回傳鏈表頭結點；

---

• 頭插法 的代碼量比 尾插法 少了三分之一，而且將 創建結點的邏輯 統一起來了，這句話什么意思呢？仔細觀察可以發現，尾插法 在實作程序中，ListCreateNode在代碼里出現了兩次，而 頭插法 只出現了一次，將流程簡化了，所以還是推薦使用 頭插法，

• 想要了解更多鏈表相關內容，可以參考：《畫解資料結構》（1 - 3）- 鏈表，

---

3、哈希表

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

一、哈希表的概念

1、查找演算法

??當我們在一個 鏈表 或者 順序表 中 查找 一個資料元素 是否存在 的時候，唯一的方法就是遍歷整個表，這種方法稱為 線性列舉，

??如果這時候，順序表是有序的情況下，我們可以采用折半的方式去查找，這種方法稱為 二分列舉，
??線性列舉 的時間復雜度為 O ( n ) O(n) O(n)，二分列舉 的時間復雜度為 O ( l o g 2 n ) O(log_2n) O(log2?n)，是否存在更快速的查找方式呢？這就是本要介紹的一種新的資料結構 —— 哈希表，

2、哈希表

??由于它不是順序結構，所以很多資料結構書上稱之為 散串列，下文會統一采用 哈希表 的形式來說明，作為讀者，只需要知道這兩者是同一種資料結構即可，
??我們把需要查找的資料，通過一個 函式映射，找到 存盤資料的位置 的程序稱為 哈希，這里涉及到幾個概念：
??a）需要 查找的資料 本身被稱為 關鍵字；
??b）通過 函式映射 將 關鍵字 變成一個 哈希值 的程序中，這里的 函式 被稱為 哈希函式；
??c）生成 哈希值 的程序程序可能產生沖突，需要進行 沖突解決；
??d）解決完沖突以后，實際 存盤資料的位置 被稱為 哈希地址，通俗的說，它就是一個陣列下標；
??e）存盤所有這些資料的資料結構就是 哈希表，程式實作上一般采用陣列實作，所以又叫 哈希陣列，整個程序如下圖所示：

2、哈希陣列

??為了方便下標索引，哈希表 的底層實作結構是一個陣列，陣列型別可以是任意型別，每個位置被稱為一個槽，如下圖所示，它代表的是一個長度為 8 的 哈希表，又叫 哈希陣列，

3、關鍵字

??關鍵字 是哈希陣列中的元素，可以是任意型別的，它可以是整型、浮點型、字符型、字串，甚至是結構體或者類，如下的 A、C、M 都可以是關鍵字；

int A = 5;
char C[100] = "Hello World!";
struct Obj { };
Obj M;

??哈希表的實作程序中，我們需要通過一些手段，將一個非整型的 關鍵字 轉換成 陣列下標，也就是 哈希值，從而通過 O ( 1 ) O(1) O(1) 的時間快速索引到它所對應的位置，
??而將一個非整型的 關鍵字 轉換成 整型 的手段就是 哈希函式，

4、哈希函式

??哈希函式可以簡單的理解為就是小學課本上那個函式，即 y = f ( x ) y = f(x) y=f(x)，這里的 f ( x ) f(x) f(x) 就是哈希函式， x x x 是關鍵字， y y y 是哈希值，好的哈希函式應該具備以下兩個特質：
??a）單射；
??b）雪崩效應：輸入值 x x x 的 1 1 1 位元的變化，能夠造成輸出值 y y y 至少一半位元的變化；
??單射很容易理解，圖 ( a ) (a) (a) 中已知哈希值 y y y 時，鍵 x x x 可能有兩種情況，不是一個單射；而圖 ( b ) (b) (b) 中已知哈希值 y y y 時，鍵 x x x 一定是唯一確定的，所以它是單射，由于 x x x 和 y y y 一一對應，這樣就從本原上減少了沖突，
??雪崩效應是為了讓哈希值更加符合隨機分布的原則，哈希表中的鍵分布的越隨機，利用率越高，效率也越高，
??常用的哈希函式有：直接定址法、除留余數法、數字分析法、平方取中法、折疊法、亂數法 等等，有關哈希函式的內容，下文會進行詳細講解，

5、哈希沖突

??哈希函式在生成 哈希值 的程序中，如果產生 不同的關鍵字得到相同的哈希值 的情況，就被稱為 哈希沖突，
??即對于哈希函式 y = f ( x ) y = f(x) y=f(x)，當關鍵字 x 1 ≠ x 2 x_1 \neq x_2 x1??=x2?，但是卻有 f ( x 1 ) = f ( x 2 ) f(x_1) = f(x_2) f(x1?)=f(x2?)，這時候，我們需要進行沖突解決，
??沖突解決方法有很多，主要有：開放定址法、再散列函式法、鏈地址法、公共溢位區法 等等，有關解決沖突的內容，下文會進行詳細講解，

6、哈希地址

??哈希地址 就是一個 陣列下標 ，即哈希陣列的下標，通過下標獲得資料，被稱為 索引，通過資料獲得下標，被稱為 哈希，平時作業的時候，和同事交流時用到的一個詞 反查 就是說的 哈希，

二、常用哈希函式

1、直接定址法

??直接定址法 就是 關鍵字 本身就是 哈希值，表示成函式值就是 f ( x ) = x f(x) = x f(x)=x??例如，我們需要統計一個字串中每個字符的出現次數，就可以通過這種方法，任何一個字符的范圍都是 [ 0 , 255 ] [0, 255] [0,255]，所以只要用一個長度為 256 的哈希陣列就可以存盤每個字符對應的出現次數，利用一次遍歷列舉就可以解決這個問題，C代碼實作如下：

int i, hash[256];
for(i = 0; str[i]; ++i) {
    ++hash[ str[i] ];
}

??這個就是最基礎的直接定址法的實作，hash[c]代表字符c在這個字串str中的出現次數，

2、平方取中法

??平方取中法 就是對 關鍵字 進行平方，再取中間的某幾位作為 哈希值，
??例如，對于關鍵字 1314 1314 1314，得到平方為 1726596 1726596 1726596，取中間三位作為哈希值，即 265 265 265，
??平方取中法 比較適用于 不清楚關鍵字的分布，且位數也不是很大 的情況，

3、折疊法

??折疊法 是將關鍵字分割成位數相等的幾部分（注意最后一部分位數不夠可以短一些），然后再進行求和，得到一個 哈希值，
??例如，對于關鍵字 5201314 5201314 5201314，將它分為四組，并且相加得到： 52 + 01 + 31 + 4 = 88 52+01+31+4 = 88 52+01+31+4=88，這就是哈希值，
??折疊法 比較適用于 不清楚關鍵字的分布，但是關鍵字位數較多 的情況，

4、除留余數法

??除留余數法 就是 關鍵字 模上 哈希表 長度，表示成函式值就是 f ( x ) = x m o d m f(x) = x \ mod \ m f(x)=x mod m??其中 m m m 代表了哈希表的長度，這種方法，不僅可以對關鍵字直接取模，也可以在 平方取中法、折疊法 之后再取模，
??例如，對于一個長度為 4 的哈希陣列，我們可以將關鍵字 模 4 得到哈希值，如圖所示：

5、位與法

??哈希陣列的長度一般選擇 2 的冪，因為我們知道取模運算是比較耗時的，而位運算相對較為高效，
??選擇 2 的冪作為陣列長度，可以將 取模運算 轉換成 二進制位與，
??令 m = 2 k m = 2^k m=2k，那么它的二進制表示就是： m = ( 1 000...000 ? k ) 2 m = (1\underbrace{000...000}_{\rm k})_2 m=(1k 000...000??)2?，任何一個數模上 m m m，就相當于取了 m m m 的二進制低 k k k 位，而 m ? 1 = ( 111...111 ? k ) 2 m-1 = (\underbrace{111...111}_{\rm k})_2 m?1=(k 111...111??)2? ，所以和 位與 m ? 1 m-1 m?1 的效果是一樣的，即： x % S = = x & ( S ? 1 ) x \ \% \ S == x \ \& \ (S - 1) x % S==x & (S?1)??除了直接定址法，其它三種方法都有可能導致哈希沖突，接下來，我們就來討論下常用的一些哈希沖突的解決方案，

三、常見哈希沖突解決方案

1、開放定址法

1）原理講解

??開放定址法 就是一旦發生沖突，就去尋找下一個空的地址，只要哈希表足夠大，總能找到一個空的位置，并且記錄下來作為它的 哈希地址，公式如下： f i ( x ) = ( f ( x ) + d i ) m o d m f_i(x) = (f(x)+d_i) \ mod \ m fi?(x)=(f(x)+di?) mod m
??這里的 d i d_i di? 是一個數列，可以是常數列 ( 1 , 1 , 1 , . . . , 1 ) (1, 1, 1, ...,1) (1,1,1,...,1)，也可以是等引數列 ( 1 , 2 , 3 , . . . , m ? 1 ) (1,2,3,...,m-1) (1,2,3,...,m?1)，

2）影片演示

??上圖中，采用的是哈希函式演算法是 除留余數法，采用的哈希沖突解決方案是 開放定址法，哈希表的每個資料就是一個關鍵字，插入之前需要先進行查找，如果找到的位置未被插入，則執行插入；否則，找到下一個未被插入的位置進行插入；總共插入了 6 個資料，分別為：11、12、13、20、19、28，
??這種方法需要注意的是，當插入資料超過哈希表長度時，不能再執行插入，

??本文在第四章講解 哈希表的現實 時采用的就是常數列的開放定址法，

2、再散列函式法

1）原理講解

??再散列函式法 就是一旦發生沖突，就采用另一個哈希函式，可以是 平方取中法、折疊法、除留余數法 等等的組合，一般用兩個哈希函式，產生沖突的概率已經微乎其微了，
??再散列函式法 能夠使關鍵字不產生聚集，當然，也會增加不少哈希函式的計算時間，

3、鏈地址法

1）原理講解

??當然，產生沖突后，我們也可以選擇不換位置，還是在原來的位置，只是把 哈希值 相同的用鏈表串聯起來，這種方法被稱為 鏈地址法，

2）影片演示

??上圖中，采用的是哈希函式演算法是 除留余數法，采用的哈希沖突解決方案是 鏈地址法，哈希表的每個資料保留了一個 鏈表頭結點 和 尾結點，插入之前需要先進行查找，如果找到的位置，鏈表非空，則插入尾結點并且更新尾結點；否則，生成一個新的鏈表頭結點和尾結點；總共插入了 6 個資料，分別為：11、12、13、20、19、28，

4、公共溢位區法

1）原理講解

??一旦產生沖突的資料，統一放到另外一個順序表中，每次查找資料，在哈希陣列中到的關鍵字和給定關鍵字相等，則認為查找成功；否則，就去公共溢位區順序查找，這種方法被稱為 公共溢位區法，
??這種方法適合沖突較少的情況，
??哈希表相關的內容，可以參考我的這篇文章：夜深人靜寫演算法（九）- 哈希表

---

4、佇列

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

一、概念

1、佇列的定義

??佇列 是僅限在 一端 進行 插入，另一端 進行 洗掉 的 線性表，
??佇列 又被稱為 先進先出 （First In First Out） 的線性表，簡稱 FIFO ，

2、隊首

??允許進行元素洗掉的一端稱為 隊首，如下圖所示：

3、隊尾

??允許進行元素插入的一端稱為 隊尾，如下圖所示：

二、介面

1、資料入隊

??佇列的插入操作，叫做 入隊，它是將 資料元素 從 隊尾 進行插入的程序，如圖所示，表示的是 插入 兩個資料（綠色 和 藍色）的程序：

2、資料出隊

??佇列的洗掉操作，叫做 出隊，它是將 隊首 元素進行洗掉的程序，如圖所示，表示的是 依次 洗掉 兩個資料（紅色 和 橙色）的程序：

3、清空佇列

??佇列的清空操作，就是一直 出隊，直到佇列為空的程序，當 隊首 和 隊尾 重合時，就代表隊尾為空了，如圖所示：

4、獲取隊首資料

??對于一個佇列來說只能獲取 隊首 資料，一般不支持獲取 其它資料，

5、獲取佇列元素個數

??佇列元素個數一般用一個額外變數存盤，入隊 時加一，出隊 時減一，這樣獲取佇列元素的時候就不需要遍歷整個佇列，通過 O ( 1 ) O(1) O(1) 的時間復雜度獲取佇列元素個數，

6、佇列的判空

??當佇列元素個數為零時，就是一個 空隊，空隊 不允許 出隊 操作，
??有關佇列的更多內容，可以參考我的這篇文章：《畫解資料結構》（1 - 6）- 佇列

---

5、堆疊

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

一、概念

1、堆疊的定義

??堆疊 是僅限在 表尾 進行 插入 和 洗掉 的 線性表，
??堆疊 又被稱為 后進先出 （Last In First Out） 的線性表，簡稱 LIFO ，

2、堆疊頂

??堆疊 是一個線性表，我們把允許 插入 和 洗掉 的一端稱為 堆疊頂，

3、堆疊底

??和 堆疊頂 相對，另一端稱為 堆疊底，實際上，堆疊底的元素我們不需要關心，

二、介面

1、資料入堆疊

??堆疊的插入操作，叫做 入堆疊，也可稱為 進堆疊、壓堆疊，如下圖所示，代表了三次入堆疊操作：

2、資料出堆疊

??堆疊的洗掉操作，叫做 出堆疊，也可稱為 彈堆疊，如下圖所示，代表了兩次出堆疊操作：

3、清空堆疊

??一直 出堆疊，直到堆疊為空，如下圖所示：

1、獲取堆疊頂資料

??對于一個堆疊來說只能獲取 堆疊頂 資料，一般不支持獲取 其它資料，

2、獲取堆疊元素個數

??堆疊元素個數一般用一個額外變數存盤，入堆疊 時加一，出堆疊 時減一，這樣獲取堆疊元素的時候就不需要遍歷整個堆疊，通過 O ( 1 ) O(1) O(1) 的時間復雜度獲取堆疊元素個數，

3、堆疊的判空

??當堆疊元素個數為零時，就是一個空堆疊，空堆疊不允許 出堆疊 操作，
??堆疊相關的內容，可以參考我的這篇文章：《畫解資料結構》（1 - 5）- 堆疊

---

🌵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，這樣就使得條件不滿足跳出回圈），

---

三、四個入門演算法

1、排序

• 一般網上的文章在講各種 「 排序 」 演算法的時候，都會甩出一張 「 思維導圖 」，如下：

• 當然，我也不例外……
• 這些概念也不用多說，只要你能夠把「 快速排序 」的思想理解了，基本上其它演算法的思想也都能學會，這個思路就是經典的：「 要學就學最難的，其它肯定能學會 」，因為當你連「 最難的 」都已經 「 KO 」 了，其它的還不是「 小菜一碟 」？信心自然就來了，
• 我們要戰勝的其實不是「 演算法 」本身，而是我們對 「 演算法 」 的恐懼，一旦建立起「 自信心 」，后面的事情，就「 水到渠成 」了，
• 然而，實際情況比這可要簡單得多，實際在上機刷題的程序中，不可能讓你手寫一個排序，你只需要知道 C++ 中 STL 的 sort 函式就夠了，它的底層就是由【快速排序】實作的，
• 所有的排序題都可以做，我挑一個來說，至于上面說到的那十個排序演算法，如果有緣，我會在八月份的這個專欄 ??《畫解資料結構》導航 ?? 中更新，盡情期待~~

I、例題描述

??給你兩個有序整數陣列 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]
??原題出處： LeetCode 88. 合并兩個有序陣列

II、基礎框架

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

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    }
};

III、思路分析

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

IV、時間復雜度

• 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)，

IV、原始碼詳解

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進行排序；

VI、本題小知識

??只要能夠達到最終的結果， O ( n ) O(n) O(n) 和 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n) 的差距其實并沒有那么大，只要是和有序相關的，就可以呼叫這個函式，直接就出來了，

---

2、線性迭代

• 迭代就是一件事情重復的做，干的事情一樣，只是引數的不同，一般配合的 資料結構 是 【陣列】 或者 【鏈表】，實作方式也是一個回圈，比 列舉 稍微復雜一點，

I、例題描述

??給定單鏈表的頭節點 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]
??原題出處： LeetCode 206. 反轉鏈表

II、基礎框架

• 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，
• 回傳的是鏈表頭結點；

III、思路分析

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

IV、時間復雜度

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

V、原始碼詳解

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) 如果沒有，則跳出迭代，

VI、本題小知識

??復雜問題簡單化的最好辦法就是將問題拆細，比如這個問題中，將一個節點取出來插到頭部這件事情可以分為兩步：
??1）洗掉給定節點；
??2）將洗掉的節點插入頭部；

---

3、線性列舉

• 線性列舉，一般配合的 資料結構 是 【陣列】 或者 【鏈表】，實作方式就是一個回圈，正因為只有一個回圈，所以線性列舉解決的問題一般比較簡單，而且很容易從題目中看出來，

I、例題描述

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

II、基礎框架

• c++ 版本給出的基礎框架代碼如下，要求不采用任何的輔助陣列；
• 也就是空間復雜度要求 O ( 1 ) O(1) O(1)，

class Solution {
public:
    void reverseString(vector<char>& s) {
    }
};

III、思路分析

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

IV、時間復雜度

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

IV、原始碼詳解

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]，

VI、本題小知識

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

---

4、二分列舉

• 能用二分列舉的問題，一定可以用線性列舉來實作，只是時間上的差別，二分列舉的時間復雜度一般為對數級，效率上會高不少，同時，實作難度也會略微有所上升，我們通過平時開發時遇到的常見問題來舉個例子，

I、例題描述

??軟體開發的時候，會有版本的概念，由于每個版本都是基于之前的版本開發的，所以錯誤的版本之后的所有版本都是錯的，假設你有 n n n 個版本 [ 1 , 2 , . . . , n ] [1, 2, ..., n] [1,2,...,n]，你想找出導致之后所有版本出錯的第一個錯誤的版本，可以通過呼叫bool isBadVersion(version)介面來判斷版本號version是否在單元測驗中出錯，實作一個函式來查找第一個錯誤的版本，應該盡量減少對呼叫 API 的次數，
??樣例輸入： 5 5 5 和 b a d = 4 bad = 4 bad=4
??樣例輸出： 4 4 4
??原題出處： LeetCode 278. 第一個錯誤的版本

II、基礎框架

• c++ 版本給出的基礎框架代碼如下，其中bool isBadVersion(int version)是供你呼叫的 API，也就是當你呼叫這個 API 時，如果version是錯誤的，則回傳true；否則，回傳false；

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
    }
};

III、思路分析

• 由題意可得，我們呼叫它提供的 API 時，回傳值分布如下：
• 000...000111...111 000...000111...111 000...000111...111
• 其中 0 代表false，1 代表true；也就是一旦出現 1，就再也不會出現 0 了，
• 所以基于這思路，我們可以二分位置；

歸納總結為 2 種情況，如下：
??1）當前二分到的位置 m i d mid mid，給出的版本是錯誤，那么從當前位置以后的版本不需要再檢測了（因為一定也是錯誤的），并且我們可以肯定，出錯的位置一定在 [ l , m i d ] [l, mid] [l,mid]；并且 m i d mid mid 是一個可行解，記錄下來；
??2）當前二分到的位置 m i d mid mid，給出的版本是正確，則出錯位置可能在 [ m i d + 1 , r ] [mid+1, r] [mid+1,r]；

IV、時間復雜度

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

V、原始碼詳解

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        long long l = 1, r = n;             // (1)
        long long ans = (long long)n + 1;
        while(l <= r) {
            long long mid = (l + r) / 2;
            if( isBadVersion(mid) ) {       
                ans = mid;                  // (2)
                r = mid - 1;
            }else {
                l = mid + 1;                // (3)
            }
        }
        return ans;
    }
};

• ( 1 ) (1) (1) 需要這里，這里兩個區間相加可能超過 int，所以需要采用 64 位整型long long；
• ( 2 ) (2) (2) 找到錯誤版本的嫌疑區間 [ l , m i d ] [l, mid] [l,mid]，并且 m i d mid mid 是確定的候選嫌疑位置；
• ( 3 ) (3) (3) 錯誤版本不可能落在 [ l , m i d ] [l, mid] [l,mid]，所以可能在 [ m i d + 1 , r ] [mid+1, r] [mid+1,r]，需要繼續二分迭代；

VI、本題小知識
??二分時，如果區間范圍過大，int難以招架時，需要動用long long；

---

四、粉絲專屬福利

語言入門：《光天化日學C語言》(示例代碼)
語言訓練：《C語言入門100例》試用版
資料結構：《畫解資料結構》原始碼
演算法入門：《演算法入門》指引
演算法進階：《夜深人靜寫演算法》演算法模板

👇🏻 添加 博主 參加 九日集訓👇🏻