1. 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法？

1. 直接好處就是寫出性能更優(yōu)的代碼；
2. 算法，是一種解決問題的思路和方法，有機會應(yīng)用到生活和事業(yè)的其他方面；
3. 長期來看，大腦的思考能力是一個人的核心競爭能力，而算法是為數(shù)不多的能夠有效訓(xùn)練大腦思考能力的途徑之一；

2. 怎么學(xué)

1. 多思考，死記硬背不如不學(xué)
2. 一定要敲代碼，適當(dāng)刷題
3. 學(xué)習(xí)筆記，留言區(qū)互動
4. 遇到難點反復(fù)迭代

3. 結(jié)構(gòu)圖譜

image.png

10個主要數(shù)據(jù)結(jié)構(gòu)

數(shù)組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹

10個主要算法

遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法

4. 效率和資源消耗的度量衡--復(fù)雜度分析

4.1 時間復(fù)雜度

漸進時間復(fù)雜度，標(biāo)識算法的執(zhí)行時間與數(shù)據(jù)規(guī)模之間的增長關(guān)系.

1. 只關(guān)注循環(huán)執(zhí)行次數(shù)最多的那段代碼
2. 加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度
3. 乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積

4. logn表示以任意數(shù)字為底數(shù)的時間復(fù)雜度，O(log3n) = O(C * log2n) = O(log2n)

   
   
   image.png

4.2 空間復(fù)雜度

漸進空間復(fù)雜度，表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系.
注意是因為算法而額外增加的存儲空間，不包括數(shù)據(jù)本身的存儲空間；

5. 數(shù)組 & 鏈表

image.png

5.1 對比

1. 數(shù)組是內(nèi)存中連續(xù)的一塊內(nèi)存空間，初始化時，必須要有這一塊能夠滿足的內(nèi)存用以開辟；而鏈表支持動態(tài)擴容
2. 數(shù)組訪問比鏈表速度快，數(shù)組根據(jù)首地址 + 偏移量 * 元素大小 尋址，而鏈表需要遍歷；
3. 鏈表比數(shù)組插入快；

基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組和鏈表， 而后面更加復(fù)雜的 樹 隊列 圖 等等 都可以通過數(shù)組和鏈表等方式存儲， 出現(xiàn)樹 隊列 圖 等數(shù)據(jù)結(jié)構(gòu)的原因 就是為了解決 部分問題處理過程中時間復(fù)雜度過高的問題， 所以數(shù)據(jù)結(jié)構(gòu)就是為了算法而生的

5.2 如何用鏈表實現(xiàn)LRU緩存淘汰算法

1. 指導(dǎo)思想
   單向鏈表，越靠后的越是最早訪問
2. 流程
   每次獲取遍歷鏈表找到節(jié)點，找到后，刪除原位置數(shù)據(jù)，在頭節(jié)點重新插入；沒找到時，直接在頭節(jié)點插入；
   如果鏈表超過容量，則刪除最末尾節(jié)點
3. 優(yōu)化方案
   此方案每次需要遍歷鏈表，時間復(fù)雜度為O(n)，可考慮散列表來記錄每個數(shù)據(jù)的位置，將時間復(fù)雜度降到O(1);

6. 棧

見代碼

7. 隊列

見代碼

8. 遞歸算法

8.1 使用條件

1. 問題可以分解為多個子問題
2. 問題和子問題除了數(shù)據(jù)規(guī)模不同，解題思路一樣
3. 存在遞歸終止條件

8.2 遞歸常見問題及解決方案

1. 警惕堆棧溢出：可以聲明一個全局變量來控制遞歸的深度，從而避免堆棧溢出（或者改為迭代循環(huán)的非遞歸寫法）。
2. 警惕重復(fù)計算：通過某種數(shù)據(jù)結(jié)構(gòu)來保存已經(jīng)求解過的值，從而避免重復(fù)計算。

8.3 如何將遞歸改寫為非遞歸代碼？

籠統(tǒng)的講，所有的遞歸代碼都可以改寫為迭代循環(huán)的非遞歸寫法。如何做？抽象出遞推公式、初始值和邊界條件，然后用迭代循環(huán)實現(xiàn)。

9. 排序算法

實現(xiàn)代碼

image.png

在小規(guī)模數(shù)據(jù)面前，O(n2) 時間復(fù)雜度的算法并不一定比 O(nlogn) 的算法執(zhí)行時間長

10. 二分查找

O(logn) 驚人的查找速度

10.1 局限性

1. 首先，二分查找依賴的是順序表結(jié)構(gòu)，簡單點說就是數(shù)組。
2. 其次，二分查找針對的是有序數(shù)據(jù)。
3. 再次，數(shù)據(jù)量太小不適合二分查找。（順序掃即可）
4. 最后，數(shù)據(jù)量太大也不適合二分查找。（數(shù)組-連續(xù)內(nèi)存空間）

11. 散列表

11.1 散列表由來

1. 散列表來源于數(shù)組，利用數(shù)組按照下標(biāo)隨機訪問的特性；
2. 需要存儲在散列表中的數(shù)據(jù)稱為鍵，將鍵轉(zhuǎn)化為數(shù)組下標(biāo)的方法叫做散列函數(shù)，散列函數(shù)計算的結(jié)果叫做散列值，數(shù)據(jù)內(nèi)容存儲在散列值對應(yīng)的數(shù)組下標(biāo)位置；

11.2 散列沖突的解決方案

1. 開放尋址法
2. 鏈表法（常用）

為什么散列表和鏈表經(jīng)常放在一起使用？

雖然散列表支持高效的插入、刪除、查找數(shù)據(jù)，但是數(shù)據(jù)都是通過散列函數(shù)打亂存儲的，不支持排序，結(jié)合鏈表，可以做到既能快速增刪查，也能排序查詢；

redis如何用O(1)實現(xiàn)LRU算法

12. 哈希算法

將任意長度的二進制值串映射成固定長度的二進制值串，這個映射的規(guī)則就是哈希算法，而通過原始數(shù)據(jù)映射之后得到的二進制值串就是哈希值。

12.1 如何設(shè)計一個優(yōu)秀的哈希算法

1. 從哈希值不能反向推導(dǎo)出原始數(shù)據(jù)（所以哈希算法也叫單向哈希算法）；
2. 對輸入數(shù)據(jù)非常敏感，哪怕原始數(shù)據(jù)只修改了一個 Bit，最后得到的哈希值也大不相同；
3. 散列沖突的概率要很小，對于不同的原始數(shù)據(jù)，哈希值相同的概率非常小；4. 哈希算法的執(zhí)行效率要盡量高效，針對較長的文本，也能快速地計算出哈希值。

12.2 一致性哈希算法

在分布式存儲應(yīng)用中，利用一致性哈希算法，可以解決緩存等分布式系統(tǒng)的擴容、縮容導(dǎo)致數(shù)據(jù)大量搬移的難題。

image.png

13. 二叉樹

幾個概念

13.1 二叉樹有哪幾種存儲方式

1. 鏈?zhǔn)酱鎯Ψ?br> 每個節(jié)點由3個字段，其中一個存儲數(shù)據(jù)，另外兩個是指向左右子節(jié)點的指針。我們只要拎住根節(jié)點，就可以通過左右子節(jié)點的指針，把整棵樹都串起來。這種存儲方式比較常用，大部分二叉樹代碼都是通過這種方式實現(xiàn)的。
2. 順序存儲
   用數(shù)組來存儲，對于完全二叉樹，如果節(jié)點X存儲在數(shù)組中的下標(biāo)為i，那么它的左子節(jié)點的存儲下標(biāo)為2i，右子節(jié)點的下標(biāo)為2i+1，反過來，下標(biāo)i/2位置存儲的就是該節(jié)點的父節(jié)點。注意，根節(jié)點存儲在下標(biāo)為1的位置。完全二叉樹用數(shù)組來存儲時最省內(nèi)存的方式。
   
   完全二叉樹定義的由來

13.2 二叉樹的遍歷

二叉樹的遍歷

13.3 二叉查找樹

在樹中的任意一個節(jié)點，其左子樹中的每個節(jié)點的值，都要小于這個節(jié)點的值，而右子樹節(jié)點的值都大于這個節(jié)點的值

13.4 有了如此高效的散列表，為什么還需要二叉樹？

1. 散列表無序存儲，如果要有序輸出，則需要排序，而二叉樹用時間復(fù)雜度為O(n)的中序遍歷即可
2. 散列表插入時有擴容、縮容的話性能低下
3. 散列表基于數(shù)組，需要連續(xù)的內(nèi)存空間，如果數(shù)據(jù)量大，不一定滿足
4. 散列表如果hash沖突，不一定比二叉樹高效；

13.5 平衡二叉查找樹

二叉樹中任意一個節(jié)點的左右子樹的高度相差不能大于 1；
平衡二叉查找樹中“平衡”的意思，其實就是讓整棵樹左右看起來比較“對稱”、比較“平衡”，不要出現(xiàn)左子樹很高、右子樹很矮的情況。這樣就能讓整棵樹的高度相對來說低一些，相應(yīng)的插入、刪除、查找等操作的效率高一些；

13.6 紅黑樹

reference
紅黑樹是最常用的一種平衡二叉查找樹；它是「近似平衡」的。它是為了解決普通二叉查找樹在數(shù)據(jù)更新的過程中，復(fù)雜度退化的問題而產(chǎn)生的。紅黑樹的高度近似 log2n，所以它是近似平衡，插入、刪除、查找操作的時間復(fù)雜度都是 O(logn)。

• 根節(jié)點是黑色的；
• 每個葉子節(jié)點都是黑色的空節(jié)點（NIL），也就是說，葉子節(jié)點不存儲數(shù)據(jù)；
• 任何相鄰的節(jié)點都不能同時為紅色，也就是說，紅色節(jié)點是被黑色節(jié)點隔開的；
• 每個節(jié)點，從該節(jié)點到達其可達葉子節(jié)點的所有路徑，都包含相同數(shù)目的黑色節(jié)點；

13.7 紅黑樹自平衡的三種操作：左旋、右旋和變色。

左旋、右旋

1. 插入的節(jié)點必須是紅色
2. 紅黑樹的平衡過程是自底向上的遞歸操作

14. 四個基本的算法思想

前文介紹了基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法，接下來，介紹幾個更加基本的算法；確切的說，它們是算法思想，并不是具體的算法，常用來指導(dǎo)我們設(shè)計具體的算法和編碼；

14.1 貪心算法

貪心算法使用的場景有限；這種算法思想更多的是指導(dǎo)設(shè)計基礎(chǔ)算法，比如最小生成樹算法、單源最短路徑算法、霍夫曼編碼；
貪心算法的最難的一塊是如何將要解決的問題抽象成貪心算法模型，只要這一步搞定之后，貪心算法的編碼一般很簡單；
貪心算法解決問題的正確性雖然很多時候都看起來是顯而易見的，但是要嚴(yán)謹(jǐn)?shù)刈C明算法能夠得到最優(yōu)解，并不是件容易的事。所以，很多時候，我們只需要多舉幾個例子，看一下貪心算法的解決方案是否真的能得到最優(yōu)解就可以了。
因此不要刻意去記憶貪心算法的原理，多練習(xí)才是最有效的學(xué)習(xí)手段；

14.2 分治算法

核心思想就是分而治之，一般用遞歸來實現(xiàn)（分治算法是一種處理問題的思想，而遞歸是一種編程技巧）；

分治算法解決的問題需要滿足幾個條件：

• 原問題與分解成的小問題具有相同的模式；
• 原問題分解成的子問題可以獨立求解，子問題之間沒有相關(guān)性，這一點是分治算法跟動態(tài)規(guī)劃的明顯區(qū)別；
• 具有分解終止條件，也就是說，當(dāng)問題足夠小時，可以直接求解；
• 可以將子問題合并成原問題，而這個合并操作的復(fù)雜度不能太高，否則就起不到減小算法總體復(fù)雜度的效果了。

14.3 回溯算法

一句話描述就是：枚舉所有情況，剪枝掉不滿足條件的，找最優(yōu)的
回溯算法一般采用遞歸的方式來實現(xiàn)
回溯的處理思想，有點類似枚舉搜索；枚舉所有的解，找到滿足期望的解；
為了有規(guī)律地枚舉所有可能的解，避免遺漏和重復(fù)，我們把問題求解的過程分為多個階段。每個階段，我們都會面對一個岔路口，我們先隨意選一條路走，當(dāng)發(fā)現(xiàn)這條路走不通的時候（不符合期望的解），就回退到上一個岔路口，另選一種走法繼續(xù)走。
回溯算法可以用來指導(dǎo)像深度優(yōu)先搜索這種算法，除此之外，很多經(jīng)典的數(shù)學(xué)問題都可以用回溯來解決：數(shù)獨、八皇后、0-1背包、圖的著色、旅行商問題、正則表達式；

14.3.1 0-1背包問題的回溯解法

0-1背包問題的經(jīng)典解法是動態(tài)規(guī)劃，不過還有一種簡單但是沒那么高效的算法：回溯算法；

public int maxW = Integer.MIN_VALUE; //存儲背包中物品總重量的最大值
// cw表示當(dāng)前已經(jīng)裝進去的物品的重量和；i表示考察到哪個物品了；
// w背包重量；items表示每個物品的重量；n表示物品個數(shù)
// 假設(shè)背包可承受重量100，物品個數(shù)10，物品重量存儲在數(shù)組a中，那可以這樣調(diào)用函數(shù)：
// f(0, 0, a, 10, 100)
public void f(int i, int cw, int[] items, int n, int w) {
        if (i == n) { // i==n表示已經(jīng)考察完所有的物品
            if (cw > maxW && cw <= w) // 不能超過背包重量
                maxW = cw;
            return;
        }
        f(i + 1, cw, items, n, w); // 當(dāng)前物品先選擇不裝進背包
        f(i + 1, cw + items[i], items, n, w); // 又回溯回來，當(dāng)前物品裝進背包
}

14.4 動態(tài)規(guī)劃

大部分動態(tài)規(guī)劃能解決的問題，都可以通過回溯算法來解決；
上面的0-1背包問題用回溯法時間復(fù)雜度是：O(2^n)，而通過動態(tài)規(guī)劃可以將時間復(fù)雜度縮短至：O(n*w)。n 表示物品個數(shù)，w 表示背包可以承載的總重量。當(dāng)n很大時，指數(shù)級的時間復(fù)雜度要比O(n*w)高很多！
動態(tài)規(guī)劃比較適合用來求解最優(yōu)問題，比如求最大值、最小值等等，它可以非常顯著地降低時間復(fù)雜度；

適合用動態(tài)規(guī)劃解決的問題

• 一個模型
• 三個特征
  最優(yōu)子結(jié)構(gòu)、無后效性、重復(fù)子問題

動態(tài)規(guī)劃解決問題的思路：

我們把問題分解為多個階段，每個階段對應(yīng)一個決策。我們記錄每一個階段可達的狀態(tài)集合（去掉重復(fù)的），然后通過當(dāng)前階段的狀態(tài)集合，來推導(dǎo)下一個階段的狀態(tài)集合，動態(tài)地往前推進。這也是動態(tài)規(guī)劃這個名字的由來。

01背包問題的動態(tài)規(guī)劃解題過程

• 狀態(tài)轉(zhuǎn)移表法
  回溯算法實現(xiàn) - 定義狀態(tài) - 畫遞歸樹 - 找重復(fù)子問題 - 畫狀態(tài)轉(zhuǎn)移表 - 根據(jù)遞推關(guān)系填表 - 將填表過程翻譯成代碼
• 狀態(tài)轉(zhuǎn)移方程法
  找最優(yōu)子結(jié)構(gòu) - 寫狀態(tài)轉(zhuǎn)移方程 - 將狀態(tài)轉(zhuǎn)移方程翻譯成代碼

動態(tài)規(guī)劃的弊端

盡管動態(tài)規(guī)劃的執(zhí)行效率比較高，但是額外申請一個n乘w+1的二維數(shù)組，對空間的消耗比較多；所以，動態(tài)規(guī)劃是一種空間換時間的解決思路；
實際上，我們只需要一個w+1的一維數(shù)組就可解決問題；動態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移的過程，都可以基于這個一維數(shù)組來操作；

0-1背包問題的動態(tài)規(guī)劃解法：

public static int knapsack2(int[] items, int n, int w) {
  boolean[] states = new boolean[w+1]; // 默認(rèn)值false
  states[0] = true;  // 第一行的數(shù)據(jù)要特殊處理，可以利用哨兵優(yōu)化
  if (items[0] <= w) {
    states[items[0]] = true;
  }
  for (int i = 1; i < n; ++i) { // 動態(tài)規(guī)劃
    for (int j = w-items[i]; j >= 0; --j) {//把第i個物品放入背包
      if (states[j]==true) states[j+items[i]] = true;
    }
  }
  for (int i = w; i >= 0; --i) { // 輸出結(jié)果
    if (states[i] == true) return i;
  }
  return 0;
}

14.5 貪心 vs 回溯 vs 動態(tài)規(guī)劃

• 貪心
  一條路走到黑，就一次機會，只能哪邊看著順眼走哪邊
• 回溯
  一條路走到黑，無數(shù)次重來的機會，還怕我走不出來（Snapshot View）
• 動態(tài)規(guī)劃
  擁有上帝視角，手握無數(shù)平行宇宙的歷史存檔，同時發(fā)展出無數(shù)個未來（Versioned Archive View）