前言

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

「 算法和數據結構 」

10分鐘過一遍算法學習路線 | 面試 | 藍橋杯 | ACM

完整版視頻地址

專欄定位適宜人群

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

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

文章目錄

• 前言
• 一、算法和數據結構的重要性
• • 1、為什么要學習算法
  • 2、如何有效的學習
  • 3、堅持并且把它當成興趣
  • 4、首先要有語言基礎
  • 5、九日集訓
  • 6、零基礎如何學習算法
  • • 1）位運算
    • 2）線性代數
    • 3）計算幾何
    • 4）數論
    • 5）組合數學 和 概率論
  • 7、零基礎如何學習數據結構
  • 8、數據結構和算法是相輔相成的
• 二、數據結構是根基
• • 1、數組
  • • 一、概念
    • • 1、順序存儲
      • 2、存儲方式
      • 3、長度和容量
      • 4、數據結構定義
    • 二、常用接口實現
    • • 1、索引
      • 2、查找
      • 3、獲取長度
      • 4、插入
      • 5、刪除
  • 2、鏈表
  • • 一、概念
    • • 1、鏈表定義
      • 2、結點結構體定義
      • 3、結點的創建
    • 二、鏈表的創建 - 尾插法
    • • 1、算法描述
      • 2、動畫演示
      • 3、源碼詳解
    • 三、鏈表的創建 - 頭插法
    • • 1、算法描述
      • 2、動畫演示
      • 3、源碼詳解
  • 3、哈希表
  • • 一、哈希表的概念
    • • 1、查找算法
      • 2、哈希表
      • 2、哈希數組
      • 3、關鍵字
      • 4、哈希函數
      • 5、哈希沖突
      • 6、哈希地址
    • 二、常用哈希函數
    • • 1、直接定址法
      • 2、平方取中法
      • 3、折疊法
      • 4、除留余數法
      • 5、位與法
    • 三、常見哈希沖突解決方案
    • • 1、開放定址法
      • • 1）原理講解
        • 2）動畫演示
      • 2、再散列函數法
      • • 1）原理講解
      • 3、鏈地址法
      • • 1）原理講解
        • 2）動畫演示
      • 4、公共溢出區法
      • • 1）原理講解
  • 4、隊列
  • • 一、概念
    • • 1、隊列的定義
      • 2、隊首
      • 3、隊尾
    • 二、接口
    • • 1、數據入隊
      • 2、數據出隊
      • 3、清空隊列
      • 4、獲取隊首數據
      • 5、獲取隊列元素個數
      • 6、隊列的判空
  • 5、棧
  • • 一、概念
    • • 1、棧的定義
      • 2、棧頂
      • 3、棧底
    • 二、接口
    • • 1、數據入棧
      • 2、數據出棧
      • 3、清空棧
      • 1、獲取棧頂數據
      • 2、獲取棧元素個數
      • 3、棧的判空
  • 🌵7、二叉樹
  • 🌳8、多叉樹
  • 🌲9、森林
  • 🍀10、樹狀數組
  • 🌍11、圖
• 三、四個入門算法
• • 1、排序
  • 2、線性迭代
  • 3、線性枚舉
  • 4、二分枚舉
• 四、粉絲專屬福利

一、算法和數據結構的重要性

1、為什么要學習算法

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

2、如何有效的學習

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

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

??相信看我文章的大多數都是「 大學生 」，能上大學的都是「 精英 」，那么我們自然要「 精益求精 」，如果你還是「 大一 」，那么太好了，你擁有大把時間，當然你可以選擇「 刷劇 」，然而，「 學好算法 」，三年后的你自然「 不能同日而語 」。
??如果你滿足如下：
?? $(1)$ 有強烈欲望「 想要學好C語言 」的人
?? $(2)$ 有強烈欲望「 想要學好C++ 」的人
?? $(3)$ 有強烈欲望「 想要學好數據結構 」的人
?? $(4)$ 有強烈欲望「 想學好算法 」的人
?? $(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)$

一、概念

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)$ 數組類型為DataType，定義為int；
• $(2)$ SeqList定義的就是一個最多存放MAXN個元素的數組，MAXN代表數組容量；
• $(3)$ length代表數組長度，即當前的元素個數。

二、常用接口實現

1、索引

??索引 就是通過 數組下標 尋找 數組元素 的過程。C語言實現如下：

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

• $(1)$ 調用方需要注意 $i$ 的取值必須為非負整數，且小于數組最大長度。否則有可能導致異常，引發崩潰。
• 索引的算法時間復雜度為 $O(1)$。
  

2、查找

??查找 就是通過 數組元素 尋找 數組下標 的過程，是索引的逆過程。
??對于有序數組，可以采用 二分 進行查找，時間復雜度為 $O(lo{g}_{2}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)$ 遍歷數組元素；
• $(2)$ 對數組元素 和 傳入的數據進行判等，一旦發現相等就返回對應數據的下標；
• $(3)$ 當數組遍歷完還是找不到，說明這個數據肯定是不存在的，直接返回 $?1$。
  

3、獲取長度

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

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

4、插入

??插入接口定義為：在數組的第 $k$ 個元素前插入一個數 $v$。由于數組是連續存儲的，那么從 $k$ 個元素往后的元素都必須往后移動一位，當 $k=0$ 時，所有元素都必須移動，所以最壞時間復雜度為 $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)$ 當元素個數已滿時，返回 $0$ 代表插入失敗；
• $(2)$ 從第 $k$ 個數開始，每個數往后移動一個位置，注意必須逆序；
• $(3)$ 將第 $k$ 個數變成 $v$；
• $(4)$ 插入了一個數，數組長度加一；
• $(5)$ 返回 $1$ 代表插入成功；

5、刪除

??插入接口定義為：將數組的第 $k$ 個元素刪除。由于數組是連續存儲的，那么第 $k$ 個元素刪除，往后的元素勢必要往前移動一位，當 $k=0$ 時，所有元素都必須移動，所以最壞時間復雜度為 $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)$ 返回0代表刪除失敗；
• $(2)$ 從前往后；
• $(3)$ 數組長度減一；
• $(4)$ 返回1代表刪除成功；
• 想要了解更多數組相關內容，可以參考：《畫解數據結構》（1 - 1）- 數組。

---

2、鏈表

內存結構：內存空間連續不連續，看具體實現
實現難度：一般
下標訪問：不支持
分類：單向鏈表、雙向鏈表、循環鏈表、DancingLinks
插入時間復雜度：$O(1)$
查找時間復雜度：$O(n)$
刪除時間復雜度：$O(1)$

一、概念

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

1、鏈表定義

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

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

2、結點結構體定義

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

• $(1)$ 數據域：可以是任意類型，由編碼的人自行指定；這段代碼中，利用typedef將它和int同名，本文的 數據域 也會全部采用int類型進行講解；
• $(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)$ 利用系統庫函數malloc分配一塊內存空間，用來存放ListNode即鏈表結點對象；
• $(2)$ 將 數據域 置為函數傳參data；
• $(3)$ 將 指針域 置空，代表這是一個孤立的 鏈表結點；
• $(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)$ head存儲頭結點的地址，tail存儲尾結點的地址，vtx存儲當前正在插入結點的地址；
??$(2)$ 當需要創建的元素個數為 0 時，直接返回空鏈表；
??$(3)$ 創建一個 數據域 為a[0]的鏈表結點；
??$(4)$ 由于初始情況下只有一個結點，所以將鏈表頭結點head和鏈表尾結點tail都置為vtx；
??$(5)$ 從數組第 1 個元素 (0 - based) 開始，循環遍歷數組；
??$(6)$ 由于數組中第 0 個元素已經創建過了，所以這里只需要對除了第 0 個元素以外的數據創建鏈表結點；
??$(7)$ 結點創建出來后，將當前鏈表尾結點tail的 后繼結點 置為vtx；
??$(8)$ 將最近創建的結點vtx作為新的 鏈表尾結點；
??$(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)$ head存儲頭結點的地址，初始為空鏈表， vtx存儲當前正在插入結點的地址；
??$(2)$ 總共需要插入 $n$ 個結點，所以采用逆序的 $n$ 次循環；
??$(3)$ 創建一個元素值為a[i]的鏈表結點，注意，由于逆序，所以這里 $i$ 的取值為 $n?1\to 0$；
??$(4)$ 將當前創建的結點的 后繼結點 置為 鏈表的頭結點head；
??$(5)$ 將鏈表頭結點head置為vtx；
??$(6)$ 返回鏈表頭結點；

---

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

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

---

3、哈希表

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

一、哈希表的概念

1、查找算法

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

??如果這時候，順序表是有序的情況下，我們可以采用折半的方式去查找，這種方法稱為 二分枚舉。
??線性枚舉 的時間復雜度為 $O(n)$。二分枚舉 的時間復雜度為 $O(lo{g}_{2}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)$ 的時間快速索引到它所對應的位置。
??而將一個非整型的 關鍵字 轉換成 整型 的手段就是 哈希函數。

4、哈希函數

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

5、哈希沖突

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

6、哈希地址

??哈希地址 就是一個 數組下標 ，即哈希數組的下標。通過下標獲得數據，被稱為 索引。通過數據獲得下標，被稱為 哈希。平時工作的時候，和同事交流時用到的一個詞 反查 就是說的 哈希。

二、常用哈希函數

1、直接定址法

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

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

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

2、平方取中法

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

3、折疊法

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

4、除留余數法

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

5、位與法

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

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

1、開放定址法

1）原理講解

??開放定址法 就是一旦發生沖突，就去尋找下一個空的地址，只要哈希表足夠大，總能找到一個空的位置，并且記錄下來作為它的 哈希地址。公式如下：$$f_i(x)=(f(x)+d_i)modm$$
??這里的 $d_i$ 是一個數列，可以是常數列 $(1,1,1,...,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)$

一、概念

1、隊列的定義

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

2、隊首

??允許進行元素刪除的一端稱為 隊首。如下圖所示：

3、隊尾

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

二、接口

1、數據入隊

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

2、數據出隊

??隊列的刪除操作，叫做 出隊。它是將 隊首 元素進行刪除的過程，如圖所示，表示的是 依次 刪除 兩個數據（紅色 和 橙色）的過程：

3、清空隊列

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

4、獲取隊首數據

??對于一個隊列來說只能獲取 隊首 數據，一般不支持獲取 其它數據。

5、獲取隊列元素個數

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

6、隊列的判空

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

---

5、棧

內存結構：看用數組實現，還是鏈表實現
實現難度：一般
下標訪問：不支持
分類：FILO、單調棧
插入時間復雜度：$O(1)$
查找時間復雜度：理論上不支持
刪除時間復雜度：$O(1)$

一、概念

1、棧的定義

??棧 是僅限在 表尾 進行 插入 和 刪除 的 線性表。
??棧 又被稱為 后進先出 （Last In First Out） 的線性表，簡稱 LIFO 。

2、棧頂

??棧 是一個線性表，我們把允許 插入 和 刪除 的一端稱為 棧頂。

3、棧底

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

二、接口

1、數據入棧

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

2、數據出棧

??棧的刪除操作，叫做 出棧，也可稱為 彈棧。如下圖所示，代表了兩次出棧操作：

3、清空棧

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

1、獲取棧頂數據

??對于一個棧來說只能獲取 棧頂 數據，一般不支持獲取 其它數據。

2、獲取棧元素個數

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

3、棧的判空

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

---

🌵7、二叉樹

優先隊列 是 堆實現的，所以也屬于 二叉樹 范疇。它和隊列不同，不屬于線性表。
內存結構：內存結構一般不連續，但是有時候實現的時候，為了方便，一般是物理連續，邏輯不連續
實現難度：較難
下標訪問：不支持
分類：二叉樹 和 多叉樹
插入時間復雜度：看情況而定
查找時間復雜度：理論上 $O(lo{g}_{2}n)$
刪除時間復雜度：看情況而定

🌳8、多叉樹

內存結構：內存結構一般不連續，但是有時候實現的時候，為了方便，一般是物理連續，邏輯不連續
實現難度：較難
下標訪問：不支持
分類：二叉樹 和 多叉樹
插入時間復雜度：看情況而定
查找時間復雜度：理論上 $O(lo{g}_{2}n)$
刪除時間復雜度：看情況而定

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

🌲9、森林

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

🍀10、樹狀數組

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

🌍11、圖

內存結構：不一定
實現難度：難
下標訪問：不支持
分類：有向圖、無向圖
插入時間復雜度：根據算法而定
查找時間復雜度：根據算法而定
刪除時間復雜度：根據算法而定

1、圖的概念

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

2、圖的存儲

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

1）鄰接矩陣

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

2）鄰接表

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

vector<Edge> edges[maxn];

3）前向星

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

4）鏈式前向星

• 鏈式前向星和鄰接表類似，也是鏈式結構和數組結構的結合，每個結點 $i$ 都有一個鏈表，鏈表的所有數據是從 $i$ 出發的所有邊的集合（對比鄰接表存的是頂點集合），邊的表示為一個四元組 $(u,v,w,next)$，其中 $(u,v)$ 代表該條邊的有向頂點對 $u\to v$，$w$ 代表邊上的權值，$next$ 指向下一條邊。
• 具體的，我們需要一個邊的結構體數組 edge[maxm]，maxm表示邊的總數，所有邊都存儲在這個結構體數組中，并且用head[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\to 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)$，就在原有的鏈表結構的首部插入這條邊，使得每次插入的時間復雜度為 $O(1)$，所以鏈表的邊的順序和讀入順序正好是逆序的。這種結構在無論是稠密的還是稀疏的圖上都有非常好的表現，空間上沒有浪費，時間上也是最小開銷。
• 調用的時候只要通過head[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、例題描述

??給你兩個有序整數數組 $nums1$ 和 $nums2$，請你將 $nums2$ 合并到 $nums1$ 中，使 $nums1$ 成為一個有序數組。初始化 $nums1$ 和 $nums2$ 的元素數量分別為 $m$ 和 $n$ 。你可以假設 $nums1$ 的空間大小等于 $m+n$，這樣它就有足夠的空間保存來自 $nums2$ 的元素。
??樣例輸入：$nums1=[1,2,3,0,0,0],m=3,nums2=[2,5,6],n=3$
??樣例輸出： $[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(nlo{g}_{2}n)$，遍歷的時間復雜度為 $O(n)$，所以總的時間復雜度為 $O(nlo{g}_{2}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)$ 簡單合并兩個數組；
• $(2)$ 對數組1進行排序；

VI、本題小知識

??只要能夠達到最終的結果，$O(n)$ 和 $O(nlo{g}_{2}n)$ 的差距其實并沒有那么大。只要是和有序相關的，就可以調用這個函數，直接就出來了。

---

2、線性迭代

• 迭代就是一件事情重復的做，干的事情一樣，只是參數的不同。一般配合的 數據結構 是 【數組】 或者 【鏈表】，實現方式也是一個循環。比 枚舉 稍微復雜一點。

I、例題描述

??給定單鏈表的頭節點 $head$ ，要求反轉鏈表，并返回反轉后的鏈表頭。
??樣例輸入：$[1,2,3,4]$
??樣例輸出：$[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$ 即可。
• 如圖所示：
  
• 我們發現，圖中的藍色指針永遠固定在最開始的鏈表頭結點上，那么可以以它為契機，每次刪除它的next，并且插到最新的頭結點前面，不斷改變頭結點head的指向，迭代 $n?1$ 次就能得到答案了。

IV、時間復雜度

• 每個結點只會被訪問一次，執行一次頭插操作，總共 $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)$ ListNode *removeNextAndReturn(ListNode* now)函數的作用是刪除now的next節點，并且返回；
• $(2)$ 本身為空或者下一個節點為空，返回空；
• $(3)$ 將需要刪除的節點緩存起來，供后續返回；
• $(4)$ 執行刪除 now->next 的操作；
• $(5)$ doRemoveNode指向的下一個節點是將要被刪除的節點，所以doRemoveNode需要被緩存起來，不然都不知道怎么進行刪除；
• $(6)$ 沒有需要刪除的節點了就結束迭代；
• $(7)$ 刪除 doRemoveNode 的下一個節點并返回被刪除的節點；
• $(8)$ 如果有被刪除的節點，則插入頭部；
• $(9)$ 如果沒有，則跳出迭代。

VI、本題小知識

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

---

3、線性枚舉

• 線性枚舉，一般配合的 數據結構 是 【數組】 或者 【鏈表】，實現方式就是一個循環。正因為只有一個循環，所以線性枚舉解決的問題一般比較簡單，而且很容易從題目中看出來。

I、例題描述

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

II、基礎框架

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

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

III、思路分析

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

IV、時間復雜度

• 線性枚舉的過程為 $O(n)$，交換變量為 $O(1)$，兩個過程是相乘的關系，所以整個算法的時間復雜度為 $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)$ 實現一個變量交換的函數，其中&是C++中的引用，在函數傳參是經常用到，被稱為：引用傳遞(pass-by-reference)，即被調函數的形式參數雖然也作為局部變量在堆棧中開辟了內存空間
  ，但是這時存放的是由主調函數放進來的實參變量的地址。被調函數對形參的任何操作都被處理成間接尋址，即通過堆棧中存放的地址訪問主調函數中的實參變量。

簡而言之，函數調用的參數，可以傳引用，從而使得函數返回時，傳參值的改變依舊生效。

• $(2)$ 這一步是做的線性枚舉，注意枚舉范圍是 $[0,len/2?1]$。

VI、本題小知識

函數調用的參數，可以傳引用，從而使得函數返回時，傳參值的改變依舊生效。

---

4、二分枚舉

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

I、例題描述

??軟件開發的時候，會有版本的概念。由于每個版本都是基于之前的版本開發的，所以錯誤的版本之后的所有版本都是錯的。假設你有 $n$ 個版本 $[1,2,...,n]$，你想找出導致之后所有版本出錯的第一個錯誤的版本。可以通過調用bool isBadVersion(version)接口來判斷版本號version是否在單元測試中出錯。實現一個函數來查找第一個錯誤的版本。應該盡量減少對調用 API 的次數。
??樣例輸入：$5$ 和 $bad=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$$
• 其中 0 代表false，1 代表true；也就是一旦出現 1，就再也不會出現 0 了。
• 所以基于這思路，我們可以二分位置；

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

IV、時間復雜度

• 由于每次都是將區間折半，所以時間復雜度為 $O(lo{g}_{2}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)$ 需要這里，這里兩個區間相加可能超過 int，所以需要采用 64 位整型long long；
• $(2)$ 找到錯誤版本的嫌疑區間 $[l,mid]$，并且 $mid$ 是確定的候選嫌疑位置；
• $(3)$ 錯誤版本不可能落在 $[l,mid]$，所以可能在 $[mid+1,r]$，需要繼續二分迭代；

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

---

四、粉絲專屬福利

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

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

總結

以上是生活随笔為你收集整理的学算法先学数据结构？是否是无稽之谈？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。