数组
优点：
- 构建一个数组非常简单
- 能让我们在 O(1) 的时间里根据数组的下标（index）查询某个元素
缺点：
- 构建时必须分配一段连续的空间
- 查询某个元素是否存在时需要遍历整个数组，耗费 O(n) 的时间（其中，n 是元素的个数）
- 删除和添加某个元素时，同样需要耗费 O(n) 的时间
力扣：
242. 有效的字母异位词
链表
优点：
- 灵活地分配内存空间
- 能在 O(1) 时间内删除或者添加元素
缺点：
- 查询元素需要 O(n) 时间
解题技巧：
- 利用快慢指针（有时候需要用到三个指针）
- 构建一个虚假的链表头
力扣：
25. K 个一组翻转链表
栈
算法基本思想：
可以用一个单链表来实现
只关心上一次的操作
处理完成上一次的操作后，能在 O(1) 时间内查找到更前一次的操作
队列
常用的场景：
广度优先搜索
双端队列
基本实现：
可以利用一个双链表
队列的头尾两端能在 O(1) 的时间内进行数据的查看、添加和删除
常用的场景：
实现一个长度动态变化的窗口或者连续区间
力扣：
239. 滑动窗口最大值
树
树的共性：
- 结构直观
- 通过树问题来考察 递归算法 掌握的熟练程度
面试中常考的树的形状有：
- 普通二叉树
- 平衡二叉树
- 完全二叉树
- 二叉搜索树
- 四叉树
- 多叉树
- 特殊的树：红黑树、自平衡二叉搜索树
特性：
- 高度为 h 的满二叉树，有 (2^h)-1 个结点
- 具有 n 个结点的完全二叉树的高度为 log(n+1) 向上取整，或者 (logn) 向下取整+1
优秀的算法往往取决于你采取哪种数据结构
优先队列
与普通队列区别：
保证每次取出的元素是队列中优先级最高的
优先级别可自定义
最常用的场景：
从杂乱无章的数据中按照一定的顺序（或者优先级）筛选数据
本质：
二叉堆的结构，堆在英文里叫 Binary Heap
利用一个数组结构来实现完全二叉树
特性：
数组里的第一个元素 array[0] 拥有最高的优先级
给定一个下标 i，那么对于元素 array[i] 而言
▶ 父节点 对应的元素下标是 (i-1)/2
▶ 左侧子节点 对应的元素下标是 2*i + 1
▶ 右侧子节点 对应的元素下标是 2*i + 2
数组中每个元素的优先级都必须要高于它两侧子节点
其基本操作为以下两个：
向上筛选（sift up / bubble up）
向下筛选（sift down / bubble down）
另一个最重要的时间复杂度：优先队列的初始化
经验：
求前 k 大，用小根堆，求前 k 小，用大根堆。
力扣：
347. 前 K 个高频元素
图
最基本知识点如下：
- 阶、度
- 树、森林、环
- 有向图、无向图、完全有向图、完全无向图
- 连通图、连通分量
- 图的存储和表达方式：邻接矩阵、邻接链表
围绕图的算法也是各式各样：
- 图的遍历：深度优先、广度优先
- 环的检测：有向图、无向图
- 拓扑排序
- 最短路径算法：Dijkstra、Bellman-Ford、Floyd Warshall
- 连通性相关算法：Kosaraju、Tarjan、求解孤岛的数量、判断是否为树
- 图的着色、旅行商问题等
必须熟练掌握的知识点：
- 图的存储和表达方式：邻接矩阵、邻接链表
- 图的遍历：深度优先、广度优先
- 二部图的检测（Bipartite）、树的检测、环的检测：有向图、无向图
- 拓扑排序
- 联合-查找算法（Union-Find）
- 最短路径：Dijkstra、Bellman-Ford
力扣：
785. 判断二分图
前缀树
也称字典树：
这种数据结构被广泛地运用在字典查找当中
什么是字典查找？
例如：给定一系列构成字典的字符串，要求在字典当中找出所有以“ABC”开头的字符串
经典应用：
搜索框输入搜索文字，会罗列以搜索词开头的相关搜索
重要性质：
- 每个节点至少包含两个基本属性
- children：数组或者集合，罗列出每个分支当中包含的所有字符
- isEnd：布尔值，表示该节点是否为某字符串的结尾
- 根节点是空的
- 除了根节点，其他所有节点都可能是单词的结尾，叶子节点一定都是单词的结尾
排序
基本的排序算法：
- 冒泡排序（稳定）
- 插入排序（稳定）
常考的排序算法
- 归并排序（稳定）
- 快速排序（不稳定）
- 拓扑排序
其他排序算法
- 希尔排序（不稳定）
- 堆排序
- 桶排序
- 冒泡排序
算法思想：
每一轮，从杂乱无章的数组头部开始，每两个元素比较大小并进行交换；直到这一轮当中最大或最小的元素被放置在数组的尾部；然后，不断地重复这个过程，直到所有元素都排好位置。
空间复杂度：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;
}
}
}
}
- 插入排序
插入排序的算法思想：
不断地将尚未排好序的数插入到已经排好序的部分。
空间复杂度：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
}
}
与冒泡排序相比：
在冒泡排序中，经过每一轮的排序处理后，数组后端的数是排好序的；
在插入排序中，经过每一轮的排序处理后，数组前端的数都是排好序的。
力扣：
147. 对链表进行插入排序
- 归并排序
分治的思想：
归并排序的核心思想是分治，把一个复杂问题拆分成若干个子问题来求解。
归并排序的算法思想：
把数组从中间划分成两个子数组；一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素；
时间复杂度：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];
}
}
}
- 快速排序
快速排序的算法思想：
快速排序也采用了分治的思想；把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组；
最优时间复杂度：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;
}
力扣：
215. 数组中的第K个最大元素
- 拓扑排序
应用场合：
拓扑排序就是要将图论里的顶点按照相连的性质进行排序
前提：
- 必须是有向图
- 图里没有环
递归和回溯
1. 递归
递归的基本性质：函数调用本身
- 把大规模的问题不断地变小，再进行推导的过程
算法思想
- 要懂得如何将一个问题的规模变小
- 再利用从小规模问题中得出的结果
- 结合当前的值或者情况，得出最终的结果
通俗理解（自顶向下的算法）
- 把要实现的递归函数，看成已经实现好的
- 直接利用解决一些子问题
- 思考：如何根据子问题的解以及当前面对的情况得出答案
2. 回溯
回溯：利用递归的性质
- 从问题的起始点出发，不断尝试
- 返回一步甚至多步再做选择，直到抵达终点的过程
回溯算法是一种试探算法，与暴力搜索最大的区别：
在回溯算法中，是一步步向前试探，对每一步探测的情况评估，再决定是否继续，可避免走弯路
回溯算法的精华
- 出现非法的情况时，可退到之前的情景，可返回一步或多步
- 再去尝试别的路径和办法
想要采用回溯算法，就必须保证：每次都有多种尝试的可能性
解决问题的套路：
function fn(n) {
// 第一步：判断输入或者状态是否非法？
if (input/state is invalid) {
return;
}
// 第二步：判断递归是否应当结束？
if (match condition) {
return some value;
}
// 遍历所有可能出现的情况
for (all possible cases) {
// 第三步：尝试下一步的可能性
solution.push(case)
// 递归
result = fn(m)
// 第四步：回溯到上一步
solution.pop(case)
}
}
递归和回溯可以说是算法面试中最重要的算法考察点之一，很多其他算法都有它们的影子：
- 二叉树的定义和遍历
- 归并排序、快速排序
- 动态规划
- 二分搜索
熟练掌握分析递归复杂度的方法，必须得有比较扎实的数学基础，比如要牢记等差数列、等比数列等求和公式。
力扣：
39. 组合总和
52. N皇后 II
深度优先搜索
DFS 解决什么问题
DFS 解决的是连通性的问题，即给定一个起始点（或某种起始状态）和一个终点（或某种最终状态），判断是否有一条路径能从起点连接到终点。
动态规划
一种数学优化的方法，同时也是编程的方法。
重要属性：
- 最优子结构 Optimal Substructure
- 状态转移方程 f(n)
- 重叠子问题 Overlapping Sub-problems
分类：
- 线性规划
- 求解 dp[i] 形式一：第一种形式，当前所求的值仅仅依赖于有限个先前计算好的值，也就是说，dp[i] 仅仅依赖于有限个 dp[j]，其中 j < i。
- 求解 dp[i] 形式二：第二种求解 dp[i] 的形式，当前所求的值依赖于所有先前计算好的值，也就是说，dp[i] 是各个 dp[j] 的某种组合，其中 j 由 0 遍历到 i−1。
- 区间规划
0-1 背包问题
非决定性多项式：
- 时间复杂度
程序运行的时间随着问题规模扩大，增长得有多快。- 非多项式级时间复杂度
指数级复杂度，如 O(2^n)，O(3^n)
全排列算法，复杂度为 O(n!) - 多项式级时间复杂度
O(1)，O(n)，O(n * log(n))，O(n2)，O(n3) 等。
- 非多项式级时间复杂度
二分搜索算法
高频真题一
扩展：找前 k 小的数（堆），第 k 小的数（快速排序）
高频真题二
拓扑排序：
高频真题三（上）
巧妙解法题收集
416. 分割等和子集 ：可以使用背包问题解法，更巧妙的是使用：降序 + 深度搜索 + 剪枝。
