數(shù)組
優(yōu)點：
- 構建一個數(shù)組非常簡單
- 能讓我們在 O(1) 的時間里根據(jù)數(shù)組的下標（index）查詢某個元素
缺點：
- 構建時必須分配一段連續(xù)的空間
- 查詢某個元素是否存在時需要遍歷整個數(shù)組，耗費 O(n) 的時間（其中，n 是元素的個數(shù)）
- 刪除和添加某個元素時，同樣需要耗費 O(n) 的時間
力扣：
242. 有效的字母異位詞
鏈表
優(yōu)點：
- 靈活地分配內(nèi)存空間
- 能在 O(1) 時間內(nèi)刪除或者添加元素
缺點：
- 查詢元素需要 O(n) 時間
解題技巧：
- 利用快慢指針（有時候需要用到三個指針）
- 構建一個虛假的鏈表頭
力扣：
25. K 個一組翻轉鏈表
棧
算法基本思想：
可以用一個單鏈表來實現(xiàn)
只關心上一次的操作
處理完成上一次的操作后，能在 O(1) 時間內(nèi)查找到更前一次的操作
隊列
常用的場景：
廣度優(yōu)先搜索
雙端隊列
基本實現(xiàn)：
可以利用一個雙鏈表
隊列的頭尾兩端能在 O(1) 的時間內(nèi)進行數(shù)據(jù)的查看、添加和刪除
常用的場景：
實現(xiàn)一個長度動態(tài)變化的窗口或者連續(xù)區(qū)間
力扣：
239. 滑動窗口最大值
樹
樹的共性：
- 結構直觀
- 通過樹問題來考察 遞歸算法 掌握的熟練程度
面試中?？嫉臉涞男螤钣校?/p>
- 普通二叉樹
- 平衡二叉樹
- 完全二叉樹
- 二叉搜索樹
- 四叉樹
- 多叉樹
- 特殊的樹：紅黑樹、自平衡二叉搜索樹
特性：
- 高度為 h 的滿二叉樹，有 (2^h)-1 個結點
- 具有 n 個結點的完全二叉樹的高度為 log(n+1) 向上取整，或者 (logn) 向下取整+1
優(yōu)秀的算法往往取決于你采取哪種數(shù)據(jù)結構
優(yōu)先隊列
與普通隊列區(qū)別：
保證每次取出的元素是隊列中優(yōu)先級最高的
優(yōu)先級別可自定義
最常用的場景：
從雜亂無章的數(shù)據(jù)中按照一定的順序（或者優(yōu)先級）篩選數(shù)據(jù)
本質：
二叉堆的結構，堆在英文里叫 Binary Heap
利用一個數(shù)組結構來實現(xiàn)完全二叉樹
特性：
數(shù)組里的第一個元素 array[0] 擁有最高的優(yōu)先級
給定一個下標 i，那么對于元素 array[i] 而言
? 父節(jié)點 對應的元素下標是 (i-1)/2
? 左側子節(jié)點 對應的元素下標是 2*i + 1
? 右側子節(jié)點 對應的元素下標是 2*i + 2
數(shù)組中每個元素的優(yōu)先級都必須要高于它兩側子節(jié)點
其基本操作為以下兩個：
向上篩選（sift up / bubble up）
向下篩選（sift down / bubble down）
另一個最重要的時間復雜度：優(yōu)先隊列的初始化
經(jīng)驗：
求前 k 大，用小根堆，求前 k 小，用大根堆。
力扣：
347. 前 K 個高頻元素
圖
最基本知識點如下：
- 階、度
- 樹、森林、環(huán)
- 有向圖、無向圖、完全有向圖、完全無向圖
- 連通圖、連通分量
- 圖的存儲和表達方式：鄰接矩陣、鄰接鏈表
圍繞圖的算法也是各式各樣：
- 圖的遍歷：深度優(yōu)先、廣度優(yōu)先
- 環(huán)的檢測：有向圖、無向圖
- 拓撲排序
- 最短路徑算法：Dijkstra、Bellman-Ford、Floyd Warshall
- 連通性相關算法：Kosaraju、Tarjan、求解孤島的數(shù)量、判斷是否為樹
- 圖的著色、旅行商問題等
必須熟練掌握的知識點：
- 圖的存儲和表達方式：鄰接矩陣、鄰接鏈表
- 圖的遍歷：深度優(yōu)先、廣度優(yōu)先
- 二部圖的檢測（Bipartite）、樹的檢測、環(huán)的檢測：有向圖、無向圖
- 拓撲排序
- 聯(lián)合-查找算法（Union-Find）
- 最短路徑：Dijkstra、Bellman-Ford
力扣：
785. 判斷二分圖
前綴樹
也稱字典樹：
這種數(shù)據(jù)結構被廣泛地運用在字典查找當中
什么是字典查找？
例如：給定一系列構成字典的字符串，要求在字典當中找出所有以“ABC”開頭的字符串
經(jīng)典應用：
搜索框輸入搜索文字，會羅列以搜索詞開頭的相關搜索
重要性質：
- 每個節(jié)點至少包含兩個基本屬性
- children：數(shù)組或者集合，羅列出每個分支當中包含的所有字符
- isEnd：布爾值，表示該節(jié)點是否為某字符串的結尾
- 根節(jié)點是空的
- 除了根節(jié)點，其他所有節(jié)點都可能是單詞的結尾，葉子節(jié)點一定都是單詞的結尾
排序
基本的排序算法：
- 冒泡排序（穩(wěn)定）
- 插入排序（穩(wěn)定）
?？嫉呐判蛩惴?/p>
- 歸并排序（穩(wěn)定）
- 快速排序（不穩(wěn)定）
- 拓撲排序
其他排序算法
- 希爾排序（不穩(wěn)定）
- 堆排序
- 桶排序
- 冒泡排序
算法思想：
每一輪，從雜亂無章的數(shù)組頭部開始，每兩個元素比較大小并進行交換；直到這一輪當中最大或最小的元素被放置在數(shù)組的尾部；然后，不斷地重復這個過程，直到所有元素都排好位置。
空間復雜度：O(1)
時間復雜度：O(n^2)
function bubbleSort(nums) {
let hasChange = true;
for (var i = 0; i < nums.length - 1 && hasChange; i++) {
hasChange = false;
for (var j = 0; j < nums.length - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
hasChange = true;
}
}
}
}
- 插入排序
插入排序的算法思想：
不斷地將尚未排好序的數(shù)插入到已經(jīng)排好序的部分。
空間復雜度：O(1)
時間復雜度：O(n^2)
function insertionSort(nums) {
for (let i = 1, j; i < nums.length; i++) {
const tmp = nums[i];
for (j = i; j > 0 && tmp < nums[j - 1]; j--) {
nums[j] = nums[j - 1];
}
nums[j] = tmp
}
}
與冒泡排序相比：
在冒泡排序中，經(jīng)過每一輪的排序處理后，數(shù)組后端的數(shù)是排好序的；
在插入排序中，經(jīng)過每一輪的排序處理后，數(shù)組前端的數(shù)都是排好序的。
力扣：
147. 對鏈表進行插入排序
- 歸并排序
分治的思想：
歸并排序的核心思想是分治，把一個復雜問題拆分成若干個子問題來求解。
歸并排序的算法思想：
把數(shù)組從中間劃分成兩個子數(shù)組；一直遞歸地把子數(shù)組劃分成更小的子數(shù)組，直到子數(shù)組里面只有一個元素；
時間復雜度：O(nlogn)
空間復雜度：O(n)
function mergeSort(nums, left, right) {
if (left >= right) {
return;
}
const mid = left + Math.floor((right - left) / 2);
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
function merge(nums, left, mid, right){
let k = i = left, j = mid + 1;
const numsCopy = nums.slice(left, right + 1);
while (k <= right) {
if (i > mid) {
nums[k++] = numsCopy[j++ - left];
} else if (j > right) {
nums[k++] = numsCopy[i++ - left];
} else if (numsCopy[i - left] < numsCopy[j - left]) {
nums[k++] = numsCopy[i++ - left];
} else {
nums[k++] = numsCopy[j++ - left];
}
}
}
- 快速排序
快速排序的算法思想：
快速排序也采用了分治的思想；把原始的數(shù)組篩選成較小和較大的兩個子數(shù)組，然后遞歸地排序兩個子數(shù)組；
最優(yōu)時間復雜度：O(nlogn)
最差時間復雜度：O(n^2)
空間復雜度：O(logn)
function quickSort(nums, left, right) {
if (left >= right) {
return;
}
const p = partition(nums, left, right);
quickSort(nums, left, p - 1);
quickSort(nums, p + 1, right);
}
function partition(nums, left, right) {
// 每次選擇第一個值 left 進行劃分
// 也可以隨機選擇 left ~ right 中一個
swap(nums, left, right);
let i = j = left;
while(j < right) {
if (nums[j] < nums[right]) {
swap(nums, i++, j);
}
j++;
}
swap(nums, i, right);
return i;
}
- 拓撲排序
應用場合：
拓撲排序就是要將圖論里的頂點按照相連的性質進行排序
前提：
- 必須是有向圖
- 圖里沒有環(huán)
遞歸和回溯
1. 遞歸
遞歸的基本性質：函數(shù)調用本身
- 把大規(guī)模的問題不斷地變小，再進行推導的過程
算法思想
- 要懂得如何將一個問題的規(guī)模變小
- 再利用從小規(guī)模問題中得出的結果
- 結合當前的值或者情況，得出最終的結果
通俗理解（自頂向下的算法）
- 把要實現(xiàn)的遞歸函數(shù)，看成已經(jīng)實現(xiàn)好的
- 直接利用解決一些子問題
- 思考：如何根據(jù)子問題的解以及當前面對的情況得出答案
2. 回溯
回溯：利用遞歸的性質
- 從問題的起始點出發(fā)，不斷嘗試
- 返回一步甚至多步再做選擇，直到抵達終點的過程
回溯算法是一種試探算法，與暴力搜索最大的區(qū)別：
在回溯算法中，是一步步向前試探，對每一步探測的情況評估，再決定是否繼續(xù)，可避免走彎路
回溯算法的精華
- 出現(xiàn)非法的情況時，可退到之前的情景，可返回一步或多步
- 再去嘗試別的路徑和辦法
想要采用回溯算法，就必須保證：每次都有多種嘗試的可能性
解決問題的套路：
function fn(n) {
// 第一步：判斷輸入或者狀態(tài)是否非法？
if (input/state is invalid) {
return;
}
// 第二步：判斷遞歸是否應當結束？
if (match condition) {
return some value;
}
// 遍歷所有可能出現(xiàn)的情況
for (all possible cases) {
// 第三步：嘗試下一步的可能性
solution.push(case)
// 遞歸
result = fn(m)
// 第四步：回溯到上一步
solution.pop(case)
}
}
遞歸和回溯可以說是算法面試中最重要的算法考察點之一，很多其他算法都有它們的影子：
- 二叉樹的定義和遍歷
- 歸并排序、快速排序
- 動態(tài)規(guī)劃
- 二分搜索
熟練掌握分析遞歸復雜度的方法，必須得有比較扎實的數(shù)學基礎，比如要牢記等差數(shù)列、等比數(shù)列等求和公式。
力扣：
39. 組合總和
52. N皇后 II
深度優(yōu)先搜索
DFS 解決什么問題
DFS 解決的是連通性的問題，即給定一個起始點（或某種起始狀態(tài)）和一個終點（或某種最終狀態(tài)），判斷是否有一條路徑能從起點連接到終點。
動態(tài)規(guī)劃
一種數(shù)學優(yōu)化的方法，同時也是編程的方法。
重要屬性：
- 最優(yōu)子結構 Optimal Substructure
- 狀態(tài)轉移方程 f(n)
- 重疊子問題 Overlapping Sub-problems
分類：
- 線性規(guī)劃
- 求解 dp[i] 形式一：第一種形式，當前所求的值僅僅依賴于有限個先前計算好的值，也就是說，dp[i] 僅僅依賴于有限個 dp[j]，其中 j < i。
- 求解 dp[i] 形式二：第二種求解 dp[i] 的形式，當前所求的值依賴于所有先前計算好的值，也就是說，dp[i] 是各個 dp[j] 的某種組合，其中 j 由 0 遍歷到 i?1。
- 區(qū)間規(guī)劃
0-1 背包問題
非決定性多項式：
- 時間復雜度
程序運行的時間隨著問題規(guī)模擴大，增長得有多快。- 非多項式級時間復雜度
指數(shù)級復雜度，如 O(2^n)，O(3^n)
全排列算法，復雜度為 O(n!) - 多項式級時間復雜度
O(1)，O(n)，O(n * log(n))，O(n2)，O(n3) 等。
- 非多項式級時間復雜度
二分搜索算法
高頻真題一
擴展：找前 k 小的數(shù)（堆），第 k 小的數(shù)（快速排序）
高頻真題二
拓撲排序：
高頻真題三（上）
巧妙解法題收集
416. 分割等和子集 ：可以使用背包問題解法，更巧妙的是使用：降序 + 深度搜索 + 剪枝。
