引言
最近在看一本算法书《labuladong 的算法小抄》，作者对各种算法问题提炼出了基础的解法框架，能够帮助读者快速理解各算法中的精髓。这里我将此记录下来，帮助自己日后快速回顾。
回溯算法
核心框架
result = [];
def backtrack( 路径，选择列表 ):
if 满足结束条件 :
result.add( 路径);
return;
for 选择 in 选择列表 ：
做选择
backtrack( 路径，选择列表 )
撤销选择
经典例子：全排列问题
let permute = function (nums) {
const result = [];
backtrack(nums, arr, result);
return result;
};
let backtrack = function (nums, track, result) {
if (track.length === nums.length) {
result.push([...track]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (track.includes(nums[i])) {
continue;
}
track.push(nums[i]);
backtrack(nums, track, result);
track.pop();
}
};
广度优先遍历框架
核心框架：
int BFS(Node start, Node target) {
Queue<Node> q; // 核心数据结构
Set<Node> visited; // 避免走回头路
q.offer(start); // 将起点加入队列
visited.add(start);
while (q not empty) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
/* 划重点，这里判断是否到达终点 */
if (cur is target) {
return step;
}
/* 将 cur 的相邻节点加入队列 */
for (Node x : cur.adj()) {
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
}
/* 划重点，在这里更新步数 */
step++;
}
}
经典问题：二叉树的最小高度
var BFS = function (root) {
if (root === null) return 0;
const queue = [root];
let depth = 1;
while (queue.length !== 0) {
const sz = queue.length;
for (var i = 0; i < sz; i++) {
const cur = queue.shift();
if (cur.left === null && cur.right === null) {
return depth;
}
if (cur.left !== null) {
queue.push(cur.left);
}
if (cur.right !== null) {
queue.push(cur.right);
}
}
depth++;
}
};
深度优先遍历框架
深度优先遍历其实就是递归的过程 例：二叉树的先序遍历
递归
void traverse(TreeNode root) {
if (root === null) return;
/* 前序遍历的代码 */
print(root.val);
traverse(root.left);
traverse(root.right);
}
遍历
void traverse(TreeNode root) {
if (root === null) return;
Stack<Node> stack;
stack.push(root);
while (!stack.empty()) {
Node node = stack.top();
stack.pop();
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
/* 输出 */
print(node.val);
}
}
排序算法
快排
function quickSort(arr) {
// 终止条件。arr 数组小于等于 1
if (arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);
// splice 返回的是一个数组
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [],
right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
}
优化版：
① 左边界作为基准值
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
if (left >= right) {
return;
}
const pivotIndex = partition(arr, left, right);
quickSortInPlace(arr, left, pivotIndex - 1);
quickSortInPlace(arr, pivotIndex + 1, right);
}
function partition(arr, left, right) {
const pivot = arr[left];
let i = left + 1;
let j = right;
while (i <= j) {
while (i <= j && arr[i] <= pivot) {
i++;
}
while (i <= j && arr[j] >= pivot) {
j--;
}
if (i < j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[left], arr[j]] = [arr[j], arr[left]];
return j;
}
② 右边界作为基准值
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
if (left >= right) {
return;
}
const pivotIndex = partition(arr, left, right);
quickSortInPlace(arr, left, pivotIndex - 1);
quickSortInPlace(arr, pivotIndex + 1, right);
}
function partition(arr, left, right) {
const pivotIndex = right;
const pivot = arr[right];
let partitionIndex = left;
for (let i = left; i < right; i++) {
if (arr[i] < pivot) {
[arr[partitionIndex], arr[i]] = [arr[i], arr[partitionIndex]];
partitionIndex++;
}
}
[arr[partitionIndex], arr[pivotIndex]] = [
arr[pivotIndex],
arr[partitionIndex],
];
return partitionIndex;
}
归并排序
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
let idx = Math.floor(arr.length / 2);
return merge(mergeSort(arr.slice(0, idx)), mergeSort(arr.slice(idx)));
}
function merge(left, right) {
let res = [];
while (left.length && right.length) {
if (left[0] < right[0]) {
res.push(left.shift());
} else {
res.push(right.shift());
}
}
return res.concat(left).concat(right);
}
堆排序
- 建立大顶堆：最大元素位于堆顶。
- 将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换。此时数组最后一个元素最大，再排序剩余的元素。
- 从堆顶元素开始，从顶到底执行堆化操作（sift down）。完成堆化后，堆的性质得到修复。
- 重复上述步骤，循环 n - 1 轮后，即可完成数组排序。
/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
function siftDown(nums, n, i) {
while (true) {
// 判断节点 i, l, r 中值最大的节点，记为 ma
let l = 2 * i + 1;
let r = 2 * i + 2;
let ma = i;
if (l < n && nums[l] > nums[ma]) {
ma = l;
}
if (r < n && nums[r] > nums[ma]) {
ma = r;
}
// 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
if (ma === i) {
break;
}
// 交换两节点
[nums[i], nums[ma]] = [nums[ma], nums[i]];
// 循环向下堆化
i = ma;
}
}
/* 堆排序 */
function heapSort(nums) {
// 建堆操作：堆化除叶节点以外的其他所有节点
for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
siftDown(nums, nums.length, i);
}
// 从堆中提取最大元素，循环 n-1 轮
for (let i = nums.length - 1; i > 0; i--) {
// 交换根节点与最右叶节点（交换首元素与尾元素）
[nums[0], nums[i]] = [nums[i], nums[0]];
// 以根节点为起点，从顶至底进行堆化
siftDown(nums, i, 0);
}
}
滑动窗口
核心框架
let left = 0, right = 0;
while (right < s.length) {
window.add(s[right]);
right++;
while (window needs shrink) {
window.remove(s[left]);
left++;
}
}
时间复杂度为 O（N）
const slidingWindow = function (s: string, t: string) {
const need: Record<string, number> = {};
for (let c of t) {
need[c] = (need[c] || 0) + 1;
}
const window: Record<string, number> = {};
let left = 0, right = 0;
let valid = 0;
while (right < s.length) {
// c 是移入窗口的字符
let c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
while (window needs shrink) {
// d 是将移出窗口的字符
let d = s[left];
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
经典问题：字符串的排列
判断 s1 的排列之一是 s2 的 子串。
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
const checkInclusion = function (s1, s2) {
if (s1.length > s2.length) {
return false;
}
let left = 0;
let right = 0;
let valid = 0;
const window = {};
const need = {};
for (let c of t) {
need[c] = (need[c] || 0) + 1;
}
while (right < s2.length) {
const c = s2[right];
right++;
if (need[c]) {
window[c] = (window[c] || 0) + 1;
if (window[c] === need[c]) {
valid++;
}
}
while (right - left >= s1.length) {
if (valid === Object.keys(need).length) {
return true;
}
const d = s2[left];
left++;
if (need[d]) {
if (window[d] === need[d]) {
valid--;
}
window[d] -= 1;
}
}
}
return false;
};
动态规划
动态规划分为以下几步：找到 “状态” 和 “选择” => 明确 dp 数组的定义 => 寻找 “状态” 之间的关系。
通用技巧：数学归纳法
经典问题：最长递增子序列
定义 dp，dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
base case： dp[i] 初始值为 1。
假设已经知道 dp[0..4]的所有结果，如何通过这些已知结果推出 dp[5] 呢？
只需要找到结尾小于 num[5] 的子序列，将 num[5] 接到后面，看最后那个子序列长度最大。
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
经典问题：最长回文子串
dp[i][j] = dp[i + 1][j - 1] && s[i] === s[j];
因为求 i,j 需要知道 i + 1, j - 1，所以 i 从 len 开始递减。并且 i 肯定是小于等于 j 的（这样才能构成字符串），j 一开始等于 i 就可以了。
最后我们就计算出了 dp table（长方形）左下一半的值.
const n = s.length;
const dp = new Array(n).fill(false).map(() => new Array(n).fill(false));
let maxLen = 0;
let start = 0;
let end = 0;
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
if (s[i] === s[j]) {
if (j - i < 2) {
dp[i][j] = true;
} else if (dp[i + 1][j - 1]) {
dp[i][j] = true;
}
}
if (dp[i][j]) {
if (j - i + 1 > maxLen) {
maxLen = j - i + 1;
start = i;
end = j;
}
}
}
}
return s.substr(start, end - start + 1);
循环的条件也可以改一下
// 遍历所有的长度
for (let len = 1; len <= length; len++)
for (let i = 0; i < length; i++) {
let j = len + i - 1;
// 如果右边界越界，就可以退出当前循环
if (j >= s.length) {
break;
}
if (s[i] != s[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
}
常见的动态规划状态转移方程
以下是几个常见的动态规划问题和它们对应的状态转移方程示例：
斐波那契数列（Fibonacci Sequence）
dp[i] = dp[i-1] + dp[i-2]，其中 dp[i] 表示第 i 个斐波那契数。
爬楼梯问题（Climbing Stairs）
dp[i] = dp[i-1] + dp[i-2]，其中 dp[i] 表示爬到第 i 级楼梯的方法数。
背包问题（Knapsack Problem）
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])，其中 dp[i][j] 表示在前 i 个物品中选择总重量不超过 j 的最大价值，weight[i] 表示第 i 个物品的重量，value[i] 表示第 i 个物品的价值。
最长递增子序列（Longest Increasing Subsequence）
dp[i] = max(dp[j] + 1, dp[i])，其中 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度，j 为 0 到 i-1 的索引，且 nums[i] > nums[j]。
最大子数组和（Maximum Subarray Sum）
dp[i] = max(nums[i], nums[i] + dp[i-1])，其中 dp[i] 表示以第 i 个元素结尾的最大子数组和。
最长公共子序列（Longest Common Subsequence）
如果 str1[i] 等于 str2[j]，则 dp[i][j] = dp[i-1][j-1] + 1；
否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])，其中 dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子序列的长度。
编辑距离（Edit Distance
如果 word1[i] 等于 word2[j]，则 dp[i][j] = dp[i-1][j-1]；
否则，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作次数。
打家劫舍（House Robber）
dp[i] = max(dp[i-1], dp[i-2] + nums[i])，其中 dp[i] 表示前 i 个房屋能够获得的最大金额，nums[i] 表示第 i 个房屋中的金额。
最大正方形（Maximal Square）
如果 matrix[i][j] 等于 1，则 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1；
否则，dp[i][j] = 0，其中 dp[i][j] 表示以 matrix[i][j] 为右下角的最大正方形的边长。
二分查找
经典框架
function binarySearch(nums, target) {
while (left <= right) {
mid = left + (right - left) / 2;
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
经典二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
var search = function (nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
};
寻找左边界的二分查找
nums 数组中可能有重复元素，找出最左侧的 target
var search = function (nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
// 防止两个数值过大造成溢出
// const mid = left + Math.floor((left - right) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else {
// 因为是要找最左侧的数，所以 = target 的时候还是要收紧边界
// nums[mid] <= target 收缩右侧边界
right = mid - 1;
}
}
if (left >= nums.length || nums[left] !== target) {
return -1;
}
return left;
};
寻找右边界的二分查找
var search = function (nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] > target) {
right = mid - 1;
} else {
// nums[mid] <= target 收缩左侧边界
left = mid + 1;
}
}
if (right < 0 || nums[right] !== target) {
return -1;
}
return right;
};
二叉树
二叉树的遍历
二叉树遍历框架：
var traverse = function (root) {
if (root === null) {
return;
}
// 前序位置
traverse(root.left);
// 中序位置
traverse(root.right);
// 后序位置
};
前序位置的代码在刚刚进入一个二叉树节点的时候执行；
后序位置的代码在将要离开一个二叉树节点的时候执行；
中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。
二叉树的解法框架
二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。
以求二叉树的最大深度为例：
① 遍历一遍二叉树，得到答案
var res = 0;
// 记录遍历到的节点的深度
var depth = 0;
// 主函数
function maxDepth(root) {
traverse(root);
return res;
}
// 二叉树遍历框架
function traverse(root) {
if (root == null) {
return;
}
// 前序位置
depth++;
if (root.left == null && root.right == null) {
// 到达叶子节点，更新最大深度
res = Math.max(res, depth);
}
traverse(root.left);
traverse(root.right);
// 后序位置
depth--;
}
② 通过分解问题计算出答案
var maxDepth = function (root) {
if (root == null) {
return 0;
}
// 利用定义，计算左右子树的最大深度
var leftMax = maxDepth(root.left);
var rightMax = maxDepth(root.right);
// 整棵树的最大深度等于左右子树的最大深度取最大值，
// 然后再加上根节点自己
var res = Math.max(leftMax, rightMax) + 1;
return res;
};
实现一个最小堆
class MinHeap {
constructor() {
this.heap = [];
}
swap(i, j) {
const temp = this.heap[i];
this.heap[i] = this.heap[j];
this.heap[j] = temp;
}
getParentIndex(i) {
return Math.floor((i - 1) / 2);
}
getLeftChildIndex(i) {
return i * 2 + 1;
}
getRightChildIndex(i) {
return i * 2 + 2;
}
insert(value) {
this.heap.push(value);
this.heapifyUp();
}
heapifyUp() {
let index = this.heap.length - 1;
while (index > 0) {
const parentIndex = this.getParentIndex(index);
// 最小堆：父节点值小于子节点值
if (this.heap[index] >= this.heap[parentIdx]) {
break;
}
this.swap(index, parentIndex);
index = parentIdx;
}
}
remove() {
if (this.heap.length === 0) {
return;
}
const root = this.heap[0];
const end = this.heap.pop();
this.heap[0] = end;
this.heapifyDown();
return root;
}
heapifyDown() {
let index = 0;
const length = this.heap.length;
while (this.getLeftChildIndex(index) < length) {
let minIndex = this.getLeftChildIndex(index);
const rightIndex = this.getRightChildIndex(index);
if (
rightIndex < length &&
this.heap[rightIndex] < this.heap[minIndex]
) {
minIndex = rightIndex;
}
if (this.heap[index] < this.heap[minIndex]) {
break;
}
this.swap(minIndex, index);
index = minIndex;
}
}
}
实现一个堆
const defaultCmp = (x, y) => x > y; // 默认是最大堆
const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
class Heap {
/**
* 默认是最大堆
* @param {Function} cmp
*/
constructor(cmp = defaultCmp) {
this.container = [];
this.cmp = cmp;
}
insert(data) {
const { container, cmp } = this;
container.push(data);
let index = container.length - 1;
while (index) {
let parent = Math.floor((index - 1) / 2);
if (!cmp(container[index], container[parent])) {
return;
}
swap(container, index, parent);
index = parent;
}
}
extract() {
const { container, cmp } = this;
if (!container.length) {
return null;
}
swap(container, 0, container.length - 1);
const res = container.pop();
const length = container.length;
let index = 0,
exchange = index * 2 + 1;
while (exchange < length) {
// // 以最大堆的情况来说：如果有右节点，并且右节点的值大于左节点的值
let right = index * 2 + 2;
if (right < length && cmp(container[right], container[exchange])) {
exchange = right;
}
if (!cmp(container[exchange], container[index])) {
break;
}
swap(container, exchange, index);
index = exchange;
exchange = index * 2 + 1;
}
return res;
}
top() {
if (this.container.length) return this.container[0];
return null;
}
}
