【算法笔记】算法归纳整理
刷完上百道 LeetCode 题之后，出现了边际效益递减的情况：一味增加刷题量，很难再有进步的感觉。
多数题目都是一些基础题的变体，因此可以用分治的思路去对复杂内容进行解构，拆解成一些结构分而治之。
本文总结归纳一些常用方法和题型。
C++ STL 容器与常用方法
| 容器 / 类 | 方法 / 示例 | 说明 | 时间复杂度 |
|---|---|---|---|
| 常用算法 | sort(v.begin(), v.end()); | 排序（升序） | O(n log n) |
sort(v.begin(), v.end(), greater<T>); | 排序（降序） | O(n log n) | |
swap(a, b); | 交换两个变量或容器 | O(1) | |
| 数组vector | v.push_back(x); | 尾部插入 | O(1) |
v.pop_back(); | 删除尾部 | O(1) | |
v.insert(pos, x); | 在 pos 插入元素 | O(n) | |
v.insert(pos, n, x); | 插入 n 个相同元素 | O(n) | |
v.insert(pos, first, last); | 插入区间 | O(n) | |
v.erase(pos); | 删除 pos 处元素 | O(n) | |
v.erase(first, last); | 删除区间 (first,last) | O(n) | |
int n = v.size(); | 元素个数 | O(1) | |
bool b = v.empty(); | 是否为空 | O(1) | |
v.clear(); | 清空 | O(n) | |
| 哈希集合 unordered_set | s.insert(x); | 插入 | 平均 O(1) |
size_t c = s.count(x); | 是否存在（0/1） | 平均 O(1) | |
auto it = s.find(x); | 查找，返回迭代器或 end() | 平均 O(1) | |
int r = s.erase(x); | 删除元素，返回删除数量 | 平均 O(1) | |
s.clear(); | 清空 | O(n) | |
| 哈希表 unordered_map | mp.insert({k,v}); | 插入键值对 | 平均 O(1) |
auto &val = mp[key]; | 访问或插入（若不存在则默认构造） | 平均 O(1) | |
auto it = mp.find(k); | 查找，返回迭代器或 end() | 平均 O(1) | |
size_t r = mp.erase(k); | 删除元素 | 平均 O(1) | |
| 栈stack | st.push(x); | 入栈 | O(1) |
st.pop(); | 出栈（删除栈顶） | O(1) | |
auto &t = st.top(); | 访问栈顶元素 | O(1) | |
bool e = st.empty(); | 是否为空 | O(1) | |
| 双端队列deque | dq.push_back(x); | 尾部插入 | O(1) |
dq.push_front(x); | 头部插入 | O(1) | |
dq.pop_back(); | 删除尾部 | O(1) | |
dq.pop_front(); | 删除头部 | O(1) | |
auto &f = dq.front(); | 访问首元素 | O(1) | |
auto &b = dq.back(); | 访问尾元素 | O(1) | |
auto it = dq.insert(dq.begin()+i, x); | 任意位置插入，返回迭代器 | O(n) | |
auto it = dq.erase(dq.begin()+i); | 删除并返回下一个位置迭代器 | O(n) | |
| 队列queue | q.push(x); | 入队 | O(1) |
q.pop(); | 出队 | O(1) | |
auto &f = q.front(); | 访问队头 | O(1) | |
auto &b = q.back(); | 访问队尾 | O(1) | |
bool e = q.empty(); | 是否为空 | O(1) | |
| 优先队列priority_queue | pq.push(x); | 插入元素 | O(log n) |
pq.emplace(args...); | 原地构造插入 | O(log n) | |
auto t = pq.top(); | 访问堆顶元素 | O(1) | |
pq.pop(); | 删除堆顶 | O(log n) | |
| 字符串string | string sub = s.substr(pos,len); | 子串 | O(len) |
size_t idx = s.find("x"); | 查找，返回位置或 npos | O(n) | |
size_t n = s.size(); | 长度 | O(1) | |
bool e = s.empty(); | 是否为空 | O(1) | |
s += "x"; | 拼接字符串 | O(len) | |
s.replace(pos,len,"abc"); | 替换子串 | O(n) | |
| 键值对pair | pair(1,"s"); | 用 .first/.second 访问 | O(1) |
常见排序算法速查表
稳定性：指的是排序过程中，相等元素的相对顺序是否保持不变
| 排序算法 | 时间复杂度 | 是否稳定 |
|---|---|---|
| 冒泡排序 Bubble | 最好 O(n)，平均 O(n²)，最坏 O(n²) | ✅ 稳定 |
| 选择排序 Selection | O(n²) | ❌ 不稳定 |
| 插入排序 Insertion | 最好 O(n)，平均 O(n²)，最坏 O(n²) | ✅ 稳定 |
| 希尔排序 Shell | 平均 O(n^1.3)，最坏 O(n²) | ❌ 不稳定 |
| 快速排序 Quick | 最好 O(n log n)，平均 O(n log n)，最坏 O(n²) | ❌ 不稳定 |
| 归并排序 Merge | O(n log n) | ✅ 稳定 |
| 堆排序 Heap | O(n log n) | ❌ 不稳定 |
| 计数排序 Counting | O(n + k) （k 为数值范围） | ✅ 稳定 |
| 基数排序 Radix | O(n·k) （k 为位数） | ✅ 稳定 |
| 桶排序 Bucket | 平均 O(n + k)，最坏 O(n²) | ✅ 稳定（依赖子排序算法） |
动态规划常见题状态转移方程
| 题目 | 状态定义 | 状态转移方程 |
|---|---|---|
| 爬楼梯 (Climbing Stairs) | dp[i] = 到达第 i 阶的方法数 | dp[i] = dp[i-1] + dp[i-2] |
| 杨辉三角 (Pascal’s Triangle) | dp[i][j] = 第 i 行第 j 个元素 | dp[i][j] = dp[i-1][j-1] + dp[i-1][j] |
| 打家劫舍 (House Robber) | dp[i] = 前 i 个房子能偷的最大金额 | dp[i] = max(dp[i-1], dp[i-2] + nums[i]) |
| 完全平方数 (Perfect Squares) | dp[i] = 组成 i 的最少完全平方数数量 | dp[i] = min(dp[i - jxj] + 1), jxj ≤ i |
| 零钱兑换 (Coin Change) | dp[i] = 组成金额 i 的最少硬币数 | dp[i] = min(dp[i - coin] + 1) |
| 最长递增子序列 (LIS) | dp[i] = 以 nums[i] 结尾的 LIS 长度 | dp[i] = max(dp[i], dp[j] + 1), 对所有 j < i 且 nums[j] < nums[i] |
| 乘积最大子数组 (Max Product Subarray) | max_dp[i], min_dp[i] = 以 i 结尾的最大/最小积 | max_dp[i] = max(nums[i], nums[i] x max_dp[i-1], nums[i] x min_dp[i-1]) |
| 分割等和子集 (Partition Equal Subset Sum) | dp[i] = 是否能组成和为 i 的子集 | dp[i] = dp[i] 或 dp[i-num] |
| 不同路径 (Unique Paths) | dp[i][j] = 到达 (i,j) 的路径数 | dp[i][j] = dp[i-1][j] + dp[i][j-1] |
| 最小路径和 (Min Path Sum) | dp[i][j] = 到达 (i,j) 的最小路径和 | dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] |
| 最长回文子串 (Longest Palindromic Substring) | dp[i][j] = s[i…j] 是否为回文 | dp[i][j] = (s[i]==s[j]) && (j-i<2 ∨ dp[i+1][j-1]) |
| 最长公共子序列 (LCS) | dp[i][j] = text1[0…i), text2[0…j) 的 LCS 长度 | dp[i][j] = dp[i-1][j-1]+1 if 相等 else max(dp[i-1][j], dp[i][j-1]) |
| 编辑距离 (Edit Distance) | dp[i][j] = word1[0…i), word2[0…j) 的最小操作数 | dp[i][j] = min(dp[i][j]，dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+替换代价) |
经典高频题
按照题型顺序归纳：
- 一维数组：无重复字符的最长子串、数组中的第K个最大元素
- 栈：有效的括号
- 链表：反转链表、合并两个有序链表、排序链表
- 二叉树：前序遍历、中序遍历、后序遍历、层序遍历(BFS/DFS)、翻转二叉树、二叉树的右视图
- 二维数组：螺旋矩阵
- 回溯：子集
- 动态规划：打家劫舍
- 算法手撕：多头注意力(MHA)
1. 无重复字符的最长子串
数组、哈希集合、滑动窗口
int lengthOfLongestSubstring(string s) {unordered_set<char> charSet;int n = s.size();int rk = -1, ans = 0;for (int i = 0; i < n; i++){if (i != 0) {charSet.erase(s[i - 1]);}while (rk + 1 < n && !charSet.count(s[rk + 1])) {charSet.insert(s[rk + 1]);rk++;}ans = max(ans, rk - i + 1);}return ans;
}
2. 数组中的第K个最大元素
数组、快速排序
int quickselect(vector<int> &nums, int l, int r, int k) {if (l == r)return nums[k];int partition = nums[l], i = l - 1, j = r + 1;while (i < j) {do i++; while (nums[i] < partition);do j--; while (nums[j] > partition);if (i < j)swap(nums[i], nums[j]);}if (k <= j)return quickselect(nums, l, j, k);else return quickselect(nums, j + 1, r, k);
}int findKthLargest(vector<int> &nums, int k) {int n = nums.size();return quickselect(nums, 0, n - 1, n - k);
}
3. 有效的括号
栈的基本使用
bool isValid(string s) {stack<char> st;for (char c : s) {if (c == '(' || c == '[' || c == '{') {st.push(c); } else {if (st.empty()) return false;char t = st.top(); st.pop();if ((c == ')' && t != '(') ||(c == ']' && t != '[') ||(c == '}' && t != '{')) {return false;}}}return st.empty();
}
4. 反转链表
ListNode* reverseList(ListNode* head) {ListNode *prev = nullptr;ListNode *next;while (head){ next = head->next;head->next = prev;prev = head;head = next;}return prev;
}
5. 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* preHead = new ListNode(-1);ListNode* prev = preHead;while (l1 != nullptr && l2 != nullptr){if (l1->val > l2->val){prev->next = l2;l2 = l2->next;}else{prev->next = l1;l1 = l1->next;}prev = prev->next;}prev->next = (l1 == nullptr? l2 : l1);return preHead->next;
}
6. 排序链表
链表和数组的混合使用。
ListNode* sortList(ListNode* head) {ListNode* curr = head;vector<int> nums;while (curr){nums.push_back(curr->val);curr = curr->next;}sort(nums.begin(), nums.end());ListNode* dummy = new ListNode();ListNode* cur = dummy;for (int i = 0; i < nums.size(); i++){cur->next = new ListNode(nums[i]);cur = cur->next; }return dummy->next;
}
6. 二叉树的各种遍历
前序遍历：
void preorder(TreeNode *root, vector<int> &res) {if (root == nullptr) {return;}res.push_back(root->val);preorder(root->left, res);preorder(root->right, res);
}vector<int> preorderTraversal(TreeNode *root) {vector<int> res;preorder(root, res);return res;
}
中序遍历：
void inorder(TreeNode* root, vector<int>& res) {if (!root) {return;}inorder(root->left, res);res.push_back(root->val);inorder(root->right, res);
}
后序遍历：
void postorder(TreeNode *root, vector<int> &res) {if (root == nullptr) {return;}postorder(root->left, res);postorder(root->right, res);res.push_back(root->val);
}
层序遍历：
BFS 广度优先遍历：
vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if (!root) return res;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int size = q.size();vector<int> level;for (int i = 0; i < size; i++) {TreeNode* node = q.front();q.pop();level.push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}res.push_back(level);}return res;
}
DFS 深度优先遍历：
void dfs(TreeNode* node, int depth, vector<vector<int>>& res) {if (!node) return;if (depth == res.size()) {res.push_back({});}res[depth].push_back(node->val);dfs(node->left, depth + 1, res);dfs(node->right, depth + 1, res);
}
vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;dfs(root, 0, res);return res;
}
7. 翻转二叉树
TreeNode* mirrorTree(TreeNode* root) {if (root == nullptr) return nullptr;TreeNode* tmp = root->left;root->left = mirrorTree(root->right);root->right = mirrorTree(tmp);return root;
}
8. 二叉树的右视图
包含队列的基本使用
vector<int> rightSideView(TreeNode* root) {queue<TreeNode*> que;if (root != nullptr) que.push(root);vector<int> result;while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (i == (size - 1)) result.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result;
}
9. 螺旋矩阵
vector<int> spiralOrder(vector<vector<int>>& matrix) {vector<int> ans;if (matrix.empty()) return ans;int rows = matrix.size();int cols = matrix[0].size();int up = 0, down = rows - 1;int left = 0, right = cols - 1;while (true) {// 向右for (int i = left; i <= right; i++) {ans.push_back(matrix[up][i]);}up++;if (up > down) break;// 向下for (int i = up; i <= down; i++) {ans.push_back(matrix[i][right]);}right--;if (right < left) break;// 向左for (int i = right; i >= left; i--) {ans.push_back(matrix[down][i]);}down--;if (down < up) break;// 向上for (int i = down; i >= up; i--) {ans.push_back(matrix[i][left]);}left++;if (left > right) break;}return ans;
}
10. 子集
可视作回溯模板
vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> result; // 存放所有子集vector<int> path; // 当前构建的子集backtrack(nums, 0, path, result);return result;
}void backtrack(vector<int>& nums, int index,vector<int>& path, vector<vector<int>>& result) {result.push_back(path); // 每个节点都是一个子集（包括空集）for (int i = index; i < nums.size(); ++i) {path.push_back(nums[i]); // 做选择backtrack(nums, i + 1, path, result); // 递归下一层，从 i+1 开始避免重复path.pop_back(); // 撤销选择}
}
11. 打家劫舍
可视作动态规划模板
int rob(vector<int>& nums) {if (nums.empty()) {return 0;}int size = nums.size();if (size == 1) {return nums[0];}vector<int> dp = vector<int>(size, 0);dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < size; i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[size - 1];
}
12. 多头注意力
手写多头注意力实现，算法岗高频手撕。
import numpy as npdef scaled_dot_product_attention(Q, K, V):d_k = Q.shape[-1]scores = np.matmul(Q, K.transpose(0, 2, 1)) / np.sqrt(d_k)weights = np.exp(scores) / np.exp(scores).sum(axis=-1, keepdims=True)return np.matmul(weights, V)class MultiHeadAttention:def __init__(self, d_model, num_heads):assert d_model % num_heads == 0self.d_model = d_modelself.num_heads = num_headsself.d_k = d_model // num_heads# 用随机矩阵模拟 Wq, Wk, Wv, Woself.Wq = np.random.randn(d_model, d_model)self.Wk = np.random.randn(d_model, d_model)self.Wv = np.random.randn(d_model, d_model)self.Wo = np.random.randn(d_model, d_model)def split_heads(self, x, batch_size):# (batch, seq_len, d_model) -> (batch, num_heads, seq_len, d_k)return x.reshape(batch_size, -1, self.num_heads, self.d_k).transpose(0, 2, 1, 3)def forward(self, Q, K, V):batch_size = Q.shape[0]Q = np.matmul(Q, self.Wq)K = np.matmul(K, self.Wk)V = np.matmul(V, self.Wv)Q = self.split_heads(Q, batch_size)K = self.split_heads(K, batch_size)V = self.split_heads(V, batch_size)# 每个头独立计算注意力heads = scaled_dot_product_attention(Q, K, V)# 拼接所有头 (batch, seq_len, d_model)concat = heads.transpose(0, 2, 1, 3).reshape(batch_size, -1, self.d_model)return np.matmul(concat, self.Wo)