刷完上百道 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^2)，最坏 O(n^2) | 稳定 |
选择排序 Selection | O(n^2) | 不稳定 |
插入排序 Insertion | 最好 O(n)，平均 O(n^2)，最坏 O(n^2) | 稳定 |
希尔排序 Shell | 平均 O(n^1.3)，最坏 O(n^2) | 不稳定 |
快速排序 Quick | 最好 O(n log n)，平均 O(n log n)，最坏 O(n^2) | 不稳定 |
归并排序 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^2) | 稳定（依赖子排序算法） |
动态规划常见题状态转移方程
题目 | 状态定义 | 状态转移方程 |
爬楼梯 (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 np
def 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 == 0
self.d_model = d_model
self.num_heads = num_heads
self.d_k = d_model // num_heads
# 用随机矩阵模拟 Wq, Wk, Wv, Wo
self.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)