LeetCode Hot 100 — C++ 题解
·
按 LeetCode 官方分类整理，每题含思路要点 + 完整 C++ 代码。
一、哈希
1. 两数之和 (1. Two Sum)
思路：遍历时用哈希表存 值→下标，查 target - nums[i] 是否已在表中。
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); ++i) {
int need = target - nums[i];
if (mp.count(need)) return {mp[need], i};
mp[nums[i]] = i;
}
return {};
}
2. 字母异位词分组 (49. Group Anagrams)
思路：排序每个字符串作为 key，异位词分到同一组。
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (auto& s : strs) {
string key = s;
sort(key.begin(), key.end());
mp[key].push_back(s);
}
vector<vector<string>> res;
for (auto& p : mp) res.push_back(p.second);
return res;
}
3. 最长连续序列 (128. Longest Consecutive Sequence)
思路：用集合存所有数，只从连续段的起点（num-1 不存在）开始向后统计。
int longestConsecutive(vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
int ans = 0;
for (int x : s) {
if (!s.count(x - 1)) {
int len = 1;
while (s.count(x + len)) len++;
ans = max(ans, len);
}
}
return ans;
}
二、双指针
4. 移动零 (283. Move Zeroes)
思路：快指针遍历，慢指针指向待填位置，非零前移，末尾补零。
void moveZeroes(vector<int>& nums) {
int pos = 0;
for (int x : nums)
if (x != 0) nums[pos++] = x;
while (pos < nums.size()) nums[pos++] = 0;
}
5. 盛最多水的容器 (11. Container With Most Water)
思路：左右双指针，每次移动较矮的一侧，更新最大面积。
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1, ans = 0;
while (l < r) {
int h = min(height[l], height[r]);
ans = max(ans, h * (r - l));
if (height[l] < height[r]) l++;
else r--;
}
return ans;
}
6. 三数之和 (15. 3Sum)
思路：排序后固定第一个数，双指针找后两个，跳过重复。
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
int n = nums.size();
for (int i = 0; i < n - 2; ++i) {
if (i > 0 && nums[i] == nums[i-1]) continue;
int l = i + 1, r = n - 1, target = -nums[i];
while (l < r) {
int sum = nums[l] + nums[r];
if (sum == target) {
res.push_back({nums[i], nums[l], nums[r]});
while (l < r && nums[l] == nums[l+1]) l++;
while (l < r && nums[r] == nums[r-1]) r--;
l++; r--;
} else if (sum < target) l++;
else r--;
}
}
return res;
}
7. 接雨水 (42. Trapping Rain Water)
思路：左右双指针，维护两侧最大高度，矮侧移动并累加水量。
int trap(vector<int>& height) {
int l = 0, r = height.size() - 1, lmax = 0, rmax = 0, ans = 0;
while (l < r) {
lmax = max(lmax, height[l]);
rmax = max(rmax, height[r]);
if (lmax < rmax) ans += lmax - height[l++];
else ans += rmax - height[r--];
}
return ans;
}
三、滑动窗口
8. 无重复字符的最长子串 (3. Longest Substring Without Repeating Characters)
思路：滑动窗口，用数组记录字符最后出现位置，左指针跳跃。
int lengthOfLongestSubstring(string s) {
int last[128] = {0}, l = 0, ans = 0;
for (int r = 0; r < s.size(); ++r) {
l = max(l, last[s[r]]);
last[s[r]] = r + 1;
ans = max(ans, r - l + 1);
}
return ans;
}
9. 找到字符串中所有字母异位词 (438. Find All Anagrams in a String)
思路：固定长度滑动窗口，比较字符计数是否相等。
vector<int> findAnagrams(string s, string p) {
if (s.size() < p.size()) return {};
vector<int> cnt(26, 0), ans;
for (char c : p) cnt[c - 'a']++;
int l = 0, r = 0, n = s.size(), m = p.size(), diff = m;
while (r < n) {
if (--cnt[s[r++] - 'a'] >= 0) diff--;
if (r - l > m)
if (++cnt[s[l++] - 'a'] > 0) diff++;
if (diff == 0) ans.push_back(l);
}
return ans;
}
10. 和为 K 的子数组 (560. Subarray Sum Equals K)
思路：前缀和 + 哈希表记录前缀和出现次数。
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp{{0, 1}};
int sum = 0, ans = 0;
for (int x : nums) {
sum += x;
ans += mp[sum - k];
mp[sum]++;
}
return ans;
}
四、普通数组
11. 最大子数组和 (53. Maximum Subarray)
思路：Kadane 算法，当前和 = max(当前元素, 前和+当前元素)。
int maxSubArray(vector<int>& nums) {
int cur = 0, ans = INT_MIN;
for (int x : nums) {
cur = max(x, cur + x);
ans = max(ans, cur);
}
return ans;
}
12. 合并区间 (56. Merge Intervals)
思路：按左端点排序，合并重叠区间。
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
for (auto& v : intervals) {
if (res.empty() || v[0] > res.back()[1])
res.push_back(v);
else
res.back()[1] = max(res.back()[1], v[1]);
}
return res;
}
13. 轮转数组 (189. Rotate Array)
思路：整体反转 → 前 k 反转 → 后 n-k 反转。
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n;
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
14. 除自身以外数组的乘积 (238. Product of Array Except Self)
思路：前缀积 × 后缀积，输出数组先存前缀，再倒序乘后缀。
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, 1);
for (int i = 1; i < n; ++i)
ans[i] = ans[i-1] * nums[i-1];
int right = 1;
for (int i = n - 1; i >= 0; --i) {
ans[i] *= right;
right *= nums[i];
}
return ans;
}
15. 缺失的第一个正数 (41. First Missing Positive)
思路：原地哈希，将数放到对应下标位置。
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i)
while (nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i])
swap(nums[i], nums[nums[i]-1]);
for (int i = 0; i < n; ++i)
if (nums[i] != i + 1) return i + 1;
return n + 1;
}
五、矩阵
16. 矩阵置零 (73. Set Matrix Zeroes)
思路：用第一行/列作标记，两个额外变量记录第一行/列是否置零。
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool row0 = false, col0 = false;
for (int j = 0; j < n; ++j) if (matrix[0][j] == 0) row0 = true;
for (int i = 0; i < m; ++i) if (matrix[i][0] == 0) col0 = true;
for (int i = 1; i < m; ++i)
for (int j = 1; j < n; ++j)
if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;
for (int i = 1; i < m; ++i)
for (int j = 1; j < n; ++j)
if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
if (row0) for (int j = 0; j < n; ++j) matrix[0][j] = 0;
if (col0) for (int i = 0; i < m; ++i) matrix[i][0] = 0;
}
17. 螺旋矩阵 (54. Spiral Matrix)
思路：定义上下左右边界，按右→下→左→上遍历。
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
int t = 0, b = matrix.size() - 1, l = 0, r = matrix[0].size() - 1;
while (t <= b && l <= r) {
for (int j = l; j <= r; ++j) res.push_back(matrix[t][j]);
t++;
for (int i = t; i <= b; ++i) res.push_back(matrix[i][r]);
r--;
if (t <= b) for (int j = r; j >= l; --j) res.push_back(matrix[b][j]);
b--;
if (l <= r) for (int i = b; i >= t; --i) res.push_back(matrix[i][l]);
l++;
}
return res;
}
18. 旋转图像 (48. Rotate Image)
思路：先沿对角线翻转，再每行反转（转置+行反转）。
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
swap(matrix[i][j], matrix[j][i]);
for (auto& row : matrix)
reverse(row.begin(), row.end());
}
19. 搜索二维矩阵 II (240. Search a 2D Matrix II)
思路：从右上角开始，按 BST 方式搜索。
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int i = 0, j = matrix[0].size() - 1;
while (i < matrix.size() && j >= 0) {
if (matrix[i][j] == target) return true;
if (matrix[i][j] < target) i++;
else j--;
}
return false;
}
六、链表
20. 相交链表 (160. Intersection of Two Linked Lists)
思路：双指针，各走一遍自己的链表后换到对方链表，相遇点即交点。
ListNode *getIntersectionNode(ListNode *a, ListNode *b) {
ListNode *pa = a, *pb = b;
while (pa != pb) {
pa = pa ? pa->next : b;
pb = pb ? pb->next : a;
}
return pa;
}
21. 反转链表 (206. Reverse Linked List)
思路：迭代，三指针（pre/cur/next）原地反转。
ListNode* reverseList(ListNode* head) {
ListNode *pre = nullptr, *cur = head;
while (cur) {
ListNode* nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
22. 回文链表 (234. Palindrome Linked List)
思路：快慢指针找中点 → 反转后半 → 比较前后半。
bool isPalindrome(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *pre = nullptr;
while (slow) {
ListNode* nxt = slow->next;
slow->next = pre;
pre = slow;
slow = nxt;
}
while (pre) {
if (pre->val != head->val) return false;
pre = pre->next;
head = head->next;
}
return true;
}
23. 环形链表 (141. Linked List Cycle)
思路：快慢指针，相遇则有环。
bool hasCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
24. 环形链表 II (142. Linked List Cycle II)
思路：快慢指针相遇后，慢指针回头部，同步走再次相遇即入环点。
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return nullptr;
}
25. 合并两个有序链表 (21. Merge Two Sorted Lists)
思路：迭代，虚拟头节点简化边界。
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0), *cur = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; }
else { cur->next = l2; l2 = l2->next; }
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return dummy.next;
}
26. 两数相加 (2. Add Two Numbers)
思路：逐位相加，进位传递。
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(0), *cur = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
int sum = carry;
if (l1) { sum += l1->val; l1 = l1->next; }
if (l2) { sum += l2->val; l2 = l2->next; }
carry = sum / 10;
cur->next = new ListNode(sum % 10);
cur = cur->next;
}
return dummy.next;
}
27. 删除链表的倒数第 N 个结点 (19. Remove Nth Node From End of List)
思路：快指针先走 n 步，慢指针随后，快指针到末尾时慢指针即待删节点前驱。
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0, head), *fast = &dummy, *slow = &dummy;
while (n--) fast = fast->next;
while (fast->next) { slow = slow->next; fast = fast->next; }
ListNode* del = slow->next;
slow->next = slow->next->next;
delete del;
return dummy.next;
}
28. 两两交换链表中的节点 (24. Swap Nodes in Pairs)
思路：递归或迭代，每次交换两个节点。
ListNode* swapPairs(ListNode* head) {
ListNode dummy(0, head), *pre = &dummy;
while (pre->next && pre->next->next) {
ListNode *a = pre->next, *b = a->next;
a->next = b->next;
b->next = a;
pre->next = b;
pre = a;
}
return dummy.next;
}
29. K 个一组翻转链表 (25. Reverse Nodes in k-Group)
思路：递归，先检查 k 个是否存在，存在则反转这 k 个，递归处理剩余。
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode *cur = head;
for (int i = 0; i < k; ++i) {
if (!cur) return head;
cur = cur->next;
}
ListNode *pre = nullptr, *cur2 = head;
for (int i = 0; i < k; ++i) {
ListNode* nxt = cur2->next;
cur2->next = pre;
pre = cur2;
cur2 = nxt;
}
head->next = reverseKGroup(cur2, k);
return pre;
}
30. 随机链表的复制 (138. Copy List with Random Pointer)
思路：在原节点后插入拷贝节点，再设置 random，最后分离。
Node* copyRandomList(Node* head) {
if (!head) return nullptr;
for (Node *cur = head; cur; cur = cur->next->next) {
Node* cp = new Node(cur->val);
cp->next = cur->next;
cur->next = cp;
}
for (Node *cur = head; cur; cur = cur->next->next)
if (cur->random)
cur->next->random = cur->random->next;
Node dummy(0), *tail = &dummy;
for (Node *cur = head; cur; cur = cur->next) {
tail->next = cur->next;
tail = tail->next;
cur->next = cur->next->next;
}
return dummy.next;
}
31. 排序链表 (148. Sort List)
思路：归并排序（快慢指针找中点 + 递归排序 + 合并）。
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *mid = slow->next;
slow->next = nullptr;
ListNode *l = sortList(head), *r = sortList(mid);
ListNode dummy(0), *cur = &dummy;
while (l && r) {
if (l->val < r->val) { cur->next = l; l = l->next; }
else { cur->next = r; r = r->next; }
cur = cur->next;
}
cur->next = l ? l : r;
return dummy.next;
}
32. 合并 K 个升序链表 (23. Merge k Sorted Lists)
思路：优先队列（最小堆）存各链表头，每次取最小。
struct Cmp {
bool operator()(ListNode* a, ListNode* b) { return a->val > b->val; }
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, Cmp> pq;
for (auto* h : lists) if (h) pq.push(h);
ListNode dummy(0), *cur = &dummy;
while (!pq.empty()) {
cur->next = pq.top(); pq.pop();
cur = cur->next;
if (cur->next) pq.push(cur->next);
}
return dummy.next;
}
33. LRU 缓存 (146. LRU Cache)
思路：哈希表 + 双向链表，get/put 均 O(1)。
class LRUCache {
struct Node { int key, val; Node *pre, *nxt; Node(int k, int v) : key(k), val(v), pre(nullptr), nxt(nullptr) {} };
unordered_map<int, Node*> mp;
Node *head, *tail;
int cap;
void remove(Node* p) { p->pre->nxt = p->nxt; p->nxt->pre = p->pre; }
void insert(Node* p) { p->nxt = head->nxt; head->nxt->pre = p; p->pre = head; head->nxt = p; }
public:
LRUCache(int capacity) : cap(capacity) {
head = new Node(0, 0); tail = new Node(0, 0);
head->nxt = tail; tail->pre = head;
}
int get(int key) {
if (!mp.count(key)) return -1;
remove(mp[key]); insert(mp[key]);
return mp[key]->val;
}
void put(int key, int value) {
if (mp.count(key)) { remove(mp[key]); delete mp[key]; }
auto* p = new Node(key, value);
mp[key] = p; insert(p);
if (mp.size() > cap) {
auto* r = tail->pre;
remove(r); mp.erase(r->key); delete r;
}
}
};
七、二叉树
34. 二叉树的中序遍历 (94. Binary Tree Inorder Traversal)
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur || !st.empty()) {
while (cur) { st.push(cur); cur = cur->left; }
cur = st.top(); st.pop();
res.push_back(cur->val);
cur = cur->right;
}
return res;
}
35. 二叉树的最大深度 (104. Maximum Depth of Binary Tree)
int maxDepth(TreeNode* root) {
return root ? 1 + max(maxDepth(root->left), maxDepth(root->right)) : 0;
}
36. 翻转二叉树 (226. Invert Binary Tree)
TreeNode* invertTree(TreeNode* root) {
if (!root) return nullptr;
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
37. 对称二叉树 (101. Symmetric Tree)
bool isSymmetric(TreeNode* root) {
function<bool(TreeNode*, TreeNode*)> f = [&](TreeNode* l, TreeNode* r) {
if (!l && !r) return true;
if (!l || !r || l->val != r->val) return false;
return f(l->left, r->right) && f(l->right, r->left);
};
return f(root->left, root->right);
}
38. 二叉树的直径 (543. Diameter of Binary Tree)
int diameterOfBinaryTree(TreeNode* root) {
int ans = 0;
function<int(TreeNode*)> dfs = [&](TreeNode* p) -> int {
if (!p) return 0;
int l = dfs(p->left), r = dfs(p->right);
ans = max(ans, l + r);
return 1 + max(l, r);
};
dfs(root);
return ans;
}
39. 二叉树的层序遍历 (102. Binary Tree Level Order Traversal)
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> res;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
int sz = q.size();
res.push_back({});
while (sz--) {
auto* p = q.front(); q.pop();
res.back().push_back(p->val);
if (p->left) q.push(p->left);
if (p->right) q.push(p->right);
}
}
return res;
}
40. 将有序数组转换为二叉搜索树 (108. Convert Sorted Array to Binary Search Tree)
TreeNode* sortedArrayToBST(vector<int>& nums) {
function<TreeNode*(int, int)> dfs = [&](int l, int r) -> TreeNode* {
if (l > r) return nullptr;
int mid = l + (r - l) / 2;
return new TreeNode(nums[mid], dfs(l, mid-1), dfs(mid+1, r));
};
return dfs(0, nums.size() - 1);
}
41. 验证二叉搜索树 (98. Validate Binary Search Tree)
bool isValidBST(TreeNode* root) {
function<bool(TreeNode*, long, long)> dfs = [&](TreeNode* p, long lo, long hi) {
if (!p) return true;
if (p->val <= lo || p->val >= hi) return false;
return dfs(p->left, lo, p->val) && dfs(p->right, p->val, hi);
};
return dfs(root, LONG_MIN, LONG_MAX);
}
42. 二叉搜索树中第 K 小的元素 (230. Kth Smallest Element in a BST)
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur || !st.empty()) {
while (cur) { st.push(cur); cur = cur->left; }
cur = st.top(); st.pop();
if (--k == 0) return cur->val;
cur = cur->right;
}
return -1;
}
43. 二叉树的右视图 (199. Binary Tree Right Side View)
vector<int> rightSideView(TreeNode* root) {
if (!root) return {};
vector<int> res;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
int sz = q.size();
while (sz--) {
auto* p = q.front(); q.pop();
if (sz == 0) res.push_back(p->val);
if (p->left) q.push(p->left);
if (p->right) q.push(p->right);
}
}
return res;
}
44. 二叉树展开为链表 (114. Flatten Binary Tree to Linked List)
思路：先序遍历顺序展开，递归时将右子树接到左子树的最右节点。
void flatten(TreeNode* root) {
if (!root) return;
flatten(root->left);
flatten(root->right);
TreeNode* r = root->right;
root->right = root->left;
root->left = nullptr;
TreeNode* p = root;
while (p->right) p = p->right;
p->right = r;
}
45. 从前序与中序遍历序列构造二叉树 (105. Construct Binary Tree from Preorder and Inorder Traversal)
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int, int> mp;
for (int i = 0; i < inorder.size(); ++i) mp[inorder[i]] = i;
int idx = 0;
function<TreeNode*(int, int)> dfs = [&](int l, int r) -> TreeNode* {
if (l > r) return nullptr;
int v = preorder[idx++];
int p = mp[v];
return new TreeNode(v, dfs(l, p-1), dfs(p+1, r));
};
return dfs(0, inorder.size() - 1);
}
46. 路径总和 III (437. Path Sum III)
思路：前缀和 + DFS，哈希表记录路径上的前缀和。
int pathSum(TreeNode* root, int targetSum) {
unordered_map<long, int> mp{{0, 1}};
int ans = 0;
function<void(TreeNode*, long)> dfs = [&](TreeNode* p, long cur) {
if (!p) return;
cur += p->val;
ans += mp[cur - targetSum];
mp[cur]++;
dfs(p->left, cur);
dfs(p->right, cur);
mp[cur]--;
};
dfs(root, 0);
return ans;
}
47. 二叉树的最近公共祖先 (236. Lowest Common Ancestor of a Binary Tree)
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
auto* l = lowestCommonAncestor(root->left, p, q);
auto* r = lowestCommonAncestor(root->right, p, q);
if (l && r) return root;
return l ? l : r;
}
48. 二叉树中的最大路径和 (124. Binary Tree Maximum Path Sum)
int maxPathSum(TreeNode* root) {
int ans = INT_MIN;
function<int(TreeNode*)> dfs = [&](TreeNode* p) -> int {
if (!p) return 0;
int l = max(dfs(p->left), 0);
int r = max(dfs(p->right), 0);
ans = max(ans, l + r + p->val);
return p->val + max(l, r);
};
dfs(root);
return ans;
}
八、图论
49. 岛屿数量 (200. Number of Islands)
思路：DFS 标记已访问的 '1'。
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size(), ans = 0;
function<void(int, int)> dfs = [&](int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') return;
grid[i][j] = '0';
dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1);
};
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == '1') { ans++; dfs(i, j); }
return ans;
}
50. 腐烂的橘子 (994. Rotting Oranges)
思路：BFS 多源起点，记录层数。
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), fresh = 0;
queue<pair<int,int>> q;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 2) q.emplace(i, j);
else if (grid[i][j] == 1) fresh++;
}
int dirs[] = {0, 1, 0, -1, 0}, steps = 0;
while (!q.empty() && fresh) {
int sz = q.size();
while (sz--) {
auto [x, y] = q.front(); q.pop();
for (int d = 0; d < 4; ++d) {
int nx = x + dirs[d], ny = y + dirs[d+1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
grid[nx][ny] = 2; fresh--;
q.emplace(nx, ny);
}
}
}
steps++;
}
return fresh ? -1 : steps;
}
51. 课程表 (207. Course Schedule)
思路：拓扑排序（Kahn），统计入度，入度为 0 的入队。
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> g(numCourses);
vector<int> indeg(numCourses, 0);
for (auto& p : prerequisites) {
g[p[1]].push_back(p[0]);
indeg[p[0]]++;
}
queue<int> q;
for (int i = 0; i < numCourses; ++i)
if (indeg[i] == 0) q.push(i);
int cnt = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); cnt++;
for (int v : g[u])
if (--indeg[v] == 0) q.push(v);
}
return cnt == numCourses;
}
52. 实现 Trie（前缀树）(208. Implement Trie (Prefix Tree))
struct TrieNode {
TrieNode* child[26] = {};
bool isEnd = false;
};
class Trie {
TrieNode* root;
public:
Trie() { root = new TrieNode(); }
void insert(string word) {
TrieNode* p = root;
for (char c : word) {
int i = c - 'a';
if (!p->child[i]) p->child[i] = new TrieNode();
p = p->child[i];
}
p->isEnd = true;
}
bool search(string word) {
TrieNode* p = root;
for (char c : word) {
int i = c - 'a';
if (!p->child[i]) return false;
p = p->child[i];
}
return p->isEnd;
}
bool startsWith(string prefix) {
TrieNode* p = root;
for (char c : prefix) {
int i = c - 'a';
if (!p->child[i]) return false;
p = p->child[i];
}
return true;
}
};
九、回溯
53. 全排列 (46. Permutations)
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
function<void(int)> dfs = [&](int idx) {
if (idx == nums.size()) { res.push_back(nums); return; }
for (int i = idx; i < nums.size(); ++i) {
swap(nums[idx], nums[i]);
dfs(idx + 1);
swap(nums[idx], nums[i]);
}
};
dfs(0);
return res;
}
54. 子集 (78. Subsets)
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> cur;
function<void(int)> dfs = [&](int idx) {
if (idx == nums.size()) { res.push_back(cur); return; }
cur.push_back(nums[idx]); dfs(idx + 1);
cur.pop_back(); dfs(idx + 1);
};
dfs(0);
return res;
}
55. 电话号码的字母组合 (17. Letter Combinations of a Phone Number)
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
vector<string> mp{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> res;
string cur;
function<void(int)> dfs = [&](int idx) {
if (idx == digits.size()) { res.push_back(cur); return; }
for (char c : mp[digits[idx] - '0']) { cur.push_back(c); dfs(idx+1); cur.pop_back(); }
};
dfs(0);
return res;
}
56. 组合总和 (39. Combination Sum)
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> cur;
function<void(int, int)> dfs = [&](int idx, int sum) {
if (sum == target) { res.push_back(cur); return; }
if (idx == candidates.size() || sum > target) return;
cur.push_back(candidates[idx]);
dfs(idx, sum + candidates[idx]);
cur.pop_back();
dfs(idx + 1, sum);
};
dfs(0, 0);
return res;
}
57. 括号生成 (22. Generate Parentheses)
vector<string> generateParenthesis(int n) {
vector<string> res;
string cur;
function<void(int, int)> dfs = [&](int l, int r) {
if (l == n && r == n) { res.push_back(cur); return; }
if (l < n) { cur.push_back('('); dfs(l+1, r); cur.pop_back(); }
if (r < l) { cur.push_back(')'); dfs(l, r+1); cur.pop_back(); }
};
dfs(0, 0);
return res;
}
58. 单词搜索 (79. Word Search)
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
function<bool(int, int, int)> dfs = [&](int i, int j, int idx) {
if (idx == word.size()) return true;
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[idx]) return false;
char c = board[i][j]; board[i][j] = '#';
bool found = dfs(i+1,j,idx+1) || dfs(i-1,j,idx+1) || dfs(i,j+1,idx+1) || dfs(i,j-1,idx+1);
board[i][j] = c;
return found;
};
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (dfs(i, j, 0)) return true;
return false;
}
59. 分割回文串 (131. Palindrome Partitioning)
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> cur;
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, false));
for (int i = n - 1; i >= 0; --i)
for (int j = i; j < n; ++j)
dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i+1][j-1]);
function<void(int)> dfs = [&](int idx) {
if (idx == n) { res.push_back(cur); return; }
for (int j = idx; j < n; ++j)
if (dp[idx][j]) { cur.push_back(s.substr(idx, j-idx+1)); dfs(j+1); cur.pop_back(); }
};
dfs(0);
return res;
}
60. N 皇后 (51. N-Queens)
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<string> board(n, string(n, '.'));
vector<bool> col(n), diag1(2*n-1), diag2(2*n-1);
function<void(int)> dfs = [&](int r) {
if (r == n) { res.push_back(board); return; }
for (int c = 0; c < n; ++c) {
int d1 = r + c, d2 = r - c + n - 1;
if (col[c] || diag1[d1] || diag2[d2]) continue;
board[r][c] = 'Q'; col[c] = diag1[d1] = diag2[d2] = true;
dfs(r + 1);
board[r][c] = '.'; col[c] = diag1[d1] = diag2[d2] = false;
}
};
dfs(0);
return res;
}
十、二分查找
61. 搜索旋转排序数组 (33. Search in Rotated Sorted Array)
思路：二分，判断 mid 落在左/右有序区间。
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) {
if (nums[l] <= target && target < nums[mid]) r = mid - 1;
else l = mid + 1;
} else {
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}
62. 在排序数组中查找元素的第一个和最后一个位置 (34. Find First and Last Position of Element in Sorted Array)
vector<int> searchRange(vector<int>& nums, int target) {
auto [l, r] = equal_range(nums.begin(), nums.end(), target);
if (l == r) return {-1, -1};
return {int(l - nums.begin()), int(r - nums.begin() - 1)};
}
63. 搜索二维矩阵 (74. Search a 2D Matrix) — 标准二分
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size(), l = 0, r = m * n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
int v = matrix[mid / n][mid % n];
if (v == target) return true;
if (v < target) l = mid + 1;
else r = mid - 1;
}
return false;
}
64. 寻找旋转排序数组中的最小值 (153. Find Minimum in Rotated Sorted Array)
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] < nums[r]) r = mid;
else l = mid + 1;
}
return nums[l];
}
65. 寻找两个正序数组的中位数 (4. Median of Two Sorted Arrays)
思路：二分较短的数组，划分使左右元素数相等。
double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
if (A.size() > B.size()) return findMedianSortedArrays(B, A);
int m = A.size(), n = B.size(), l = 0, r = m;
while (l <= r) {
int i = l + (r - l) / 2, j = (m + n + 1) / 2 - i;
int al = i > 0 ? A[i-1] : INT_MIN;
int ar = i < m ? A[i] : INT_MAX;
int bl = j > 0 ? B[j-1] : INT_MIN;
int br = j < n ? B[j] : INT_MAX;
if (al <= br && bl <= ar)
return (m + n) % 2 ? max(al, bl) : (max(al, bl) + min(ar, br)) / 2.0;
if (al > br) r = i - 1;
else l = i + 1;
}
return 0;
}
十一、栈
66. 有效括号 (20. Valid Parentheses)
bool isValid(string s) {
stack<char> st;
for (char c : s) {
if (c == '(') st.push(')');
else if (c == '[') st.push(']');
else if (c == '{') st.push('}');
else if (st.empty() || st.top() != c) return false;
else st.pop();
}
return st.empty();
}
67. 最小栈 (155. Min Stack)
class MinStack {
stack<long long> st;
long long mn;
public:
MinStack() {}
void push(int x) {
if (st.empty()) { mn = x; st.push(0); }
else { st.push(x - mn); if (x < mn) mn = x; }
}
void pop() {
if (st.top() < 0) mn -= st.top();
st.pop();
}
int top() { return st.top() < 0 ? mn : (int)(mn + st.top()); }
int getMin() { return (int)mn; }
};
68. 字符串解码 (394. Decode String)
思路：两个栈（数字、字符串）逐字符处理。
string decodeString(string s) {
stack<int> numSt;
stack<string> strSt;
string cur;
int k = 0;
for (char c : s) {
if (isdigit(c)) k = k * 10 + (c - '0');
else if (c == '[') { numSt.push(k); strSt.push(cur); k = 0; cur.clear(); }
else if (c == ']') {
string tmp = cur;
cur = strSt.top(); strSt.pop();
for (int i = numSt.top(); i > 0; --i) cur += tmp;
numSt.pop();
} else cur += c;
}
return cur;
}
69. 每日温度 (739. Daily Temperatures)
思路：单调递减栈，栈内存下标。
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n, 0);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
ans[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
return ans;
}
70. 柱状图中最大的矩形 (84. Largest Rectangle in Histogram)
思路：单调递增栈，遇到更矮时弹出并计算面积。
int largestRectangleArea(vector<int>& heights) {
heights.push_back(0);
stack<int> st;
int ans = 0;
for (int i = 0; i < heights.size(); ++i) {
while (!st.empty() && heights[i] < heights[st.top()]) {
int h = heights[st.top()]; st.pop();
int w = st.empty() ? i : i - st.top() - 1;
ans = max(ans, h * w);
}
st.push(i);
}
return ans;
}
十二、堆
71. 数组中的第 K 个最大元素 (215. Kth Largest Element in an Array)
思路：最小堆保持大小为 k，或快速选择（优化）。
// 最小堆 O(n log k)
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
for (int x : nums) { pq.push(x); if (pq.size() > k) pq.pop(); }
return pq.top();
}
72. 前 K 个高频元素 (347. Top K Frequent Elements)
思路：哈希表统计频率 → 最小堆取 top k。
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> mp;
for (int x : nums) mp[x]++;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
for (auto& [v, f] : mp) {
pq.emplace(f, v);
if (pq.size() > k) pq.pop();
}
vector<int> res;
while (!pq.empty()) { res.push_back(pq.top().second); pq.pop(); }
return res;
}
73. 数据流的中位数 (295. Find Median from Data Stream)
思路：两个堆（大顶堆存小半，小顶堆存大半），平衡大小。
class MedianFinder {
priority_queue<int> left; // 大顶堆
priority_queue<int, vector<int>, greater<int>> right; // 小顶堆
public:
void addNum(int num) {
if (left.empty() || num <= left.top()) left.push(num);
else right.push(num);
if (left.size() > right.size() + 1) { right.push(left.top()); left.pop(); }
if (right.size() > left.size()) { left.push(right.top()); right.pop(); }
}
double findMedian() {
return left.size() > right.size() ? left.top() : (left.top() + right.top()) / 2.0;
}
};
十三、贪心
74. 买卖股票的最佳时机 (121. Best Time to Buy and Sell Stock)
int maxProfit(vector<int>& prices) {
int mn = INT_MAX, ans = 0;
for (int p : prices) { mn = min(mn, p); ans = max(ans, p - mn); }
return ans;
}
75. 跳跃游戏 (55. Jump Game)
bool canJump(vector<int>& nums) {
int reach = 0;
for (int i = 0; i <= reach && i < nums.size(); ++i)
reach = max(reach, i + nums[i]);
return reach >= nums.size() - 1;
}
76. 跳跃游戏 II (45. Jump Game II)
int jump(vector<int>& nums) {
int end = 0, far = 0, ans = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
far = max(far, i + nums[i]);
if (i == end) { ans++; end = far; }
}
return ans;
}
77. 划分字母区间 (763. Partition Labels)
vector<int> partitionLabels(string s) {
int last[26] = {0};
for (int i = 0; i < s.size(); ++i) last[s[i]-'a'] = i;
vector<int> res;
int start = 0, end = 0;
for (int i = 0; i < s.size(); ++i) {
end = max(end, last[s[i]-'a']);
if (i == end) { res.push_back(end - start + 1); start = i + 1; }
}
return res;
}
十四、动态规划
78. 爬楼梯 (70. Climbing Stairs)
int climbStairs(int n) {
int a = 1, b = 1;
for (int i = 2; i <= n; ++i) { int c = a + b; a = b; b = c; }
return b;
}
79. 杨辉三角 (118. Pascal's Triangle)
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res;
for (int i = 0; i < numRows; ++i)
res.push_back(vector<int>(i + 1, 1));
for (int i = 2; i < numRows; ++i)
for (int j = 1; j < i; ++j)
res[i][j] = res[i-1][j-1] + res[i-1][j];
return res;
}
80. 打家劫舍 (198. House Robber)
int rob(vector<int>& nums) {
int a = 0, b = 0;
for (int x : nums) { int c = max(b, a + x); a = b; b = c; }
return b;
}
81. 完全平方数 (279. Perfect Squares)
int numSquares(int n) {
vector<int> dp(n + 1, n);
dp[0] = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j * j <= i; ++j)
dp[i] = min(dp[i], dp[i - j*j] + 1);
return dp[n];
}
82. 零钱兑换 (322. Coin Change)
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; ++i)
for (int c : coins)
if (c <= i) dp[i] = min(dp[i], dp[i - c] + 1);
return dp[amount] > amount ? -1 : dp[amount];
}
83. 单词拆分 (139. Word Break)
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
int n = s.size();
vector<bool> dp(n + 1, false); dp[0] = true;
for (int i = 1; i <= n; ++i)
for (int j = 0; j < i; ++j)
if (dp[j] && dict.count(s.substr(j, i - j))) { dp[i] = true; break; }
return dp[n];
}
84. 最长递增子序列 (300. Longest Increasing Subsequence)
思路：patience sorting（贪心二分），tails[i] 存长度为 i+1 的 LIS 最小末尾。
int lengthOfLIS(vector<int>& nums) {
vector<int> tails;
for (int x : nums) {
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) tails.push_back(x);
else *it = x;
}
return tails.size();
}
85. 乘积最大子数组 (152. Maximum Product Subarray)
int maxProduct(vector<int>& nums) {
int curMax = 1, curMin = 1, ans = INT_MIN;
for (int x : nums) {
int a = curMax * x, b = curMin * x;
curMax = max({x, a, b});
curMin = min({x, a, b});
ans = max(ans, curMax);
}
return ans;
}
86. 分割等和子集 (416. Partition Equal Subset Sum)
思路：0-1 背包，DP 判断能否凑出总和的一半。
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2) return false;
int target = sum / 2;
vector<bool> dp(target + 1, false); dp[0] = true;
for (int x : nums)
for (int j = target; j >= x; --j)
dp[j] = dp[j] || dp[j - x];
return dp[target];
}
87. 最长有效括号 (32. Longest Valid Parentheses)
int longestValidParentheses(string s) {
int ans = 0;
stack<int> st; st.push(-1);
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') st.push(i);
else {
st.pop();
if (st.empty()) st.push(i);
else ans = max(ans, i - st.top());
}
}
return ans;
}
十五、多维动态规划
88. 不同路径 (62. Unique Paths)
int uniquePaths(int m, int n) {
vector<int> dp(n, 1);
for (int i = 1; i < m; ++i)
for (int j = 1; j < n; ++j)
dp[j] += dp[j-1];
return dp[n-1];
}
89. 最小路径和 (64. Minimum Path Sum)
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for (int i = 1; i < m; ++i) grid[i][0] += grid[i-1][0];
for (int j = 1; j < n; ++j) grid[0][j] += grid[0][j-1];
for (int i = 1; i < m; ++i)
for (int j = 1; j < n; ++j)
grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
return grid[m-1][n-1];
}
90. 最长回文子串 (5. Longest Palindromic Substring)
string longestPalindrome(string s) {
int n = s.size(), l = 0, maxLen = 0;
for (int i = 0; i < n; ++i) {
for (int d : {0, 1}) { // 奇数/偶数扩展
int left = i, right = i + d;
while (left >= 0 && right < n && s[left] == s[right]) { left--; right++; }
int len = right - left - 1;
if (len > maxLen) { maxLen = len; l = left + 1; }
}
}
return s.substr(l, maxLen);
}
91. 最长公共子序列 (1143. Longest Common Subsequence)
int longestCommonSubsequence(string a, string b) {
int m = a.size(), n = b.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
return dp[m][n];
}
92. 编辑距离 (72. Edit Distance)
int minDistance(string a, string b) {
int m = a.size(), n = b.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 0; i <= m; ++i) dp[i][0] = i;
for (int j = 0; j <= n; ++j) dp[0][j] = j;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
return dp[m][n];
}
十六、技巧
93. 只出现一次的数字 (136. Single Number)
int singleNumber(vector<int>& nums) {
int ans = 0;
for (int x : nums) ans ^= x;
return ans;
}
94. 多数元素 (169. Majority Element)
int majorityElement(vector<int>& nums) {
int cnt = 0, cand = 0;
for (int x : nums) {
if (cnt == 0) cand = x;
cnt += (x == cand) ? 1 : -1;
}
return cand;
}
95. 颜色分类 (75. Sort Colors)
思路：三指针（荷兰国旗问题）。
void sortColors(vector<int>& nums) {
int l = 0, m = 0, r = nums.size() - 1;
while (m <= r) {
if (nums[m] == 0) swap(nums[l++], nums[m++]);
else if (nums[m] == 1) m++;
else swap(nums[m], nums[r--]);
}
}
96. 下一个排列 (31. Next Permutation)
void nextPermutation(vector<int>& nums) {
int i = nums.size() - 2;
while (i >= 0 && nums[i] >= nums[i+1]) i--;
if (i >= 0) {
int j = nums.size() - 1;
while (nums[j] <= nums[i]) j--;
swap(nums[i], nums[j]);
}
reverse(nums.begin() + i + 1, nums.end());
}
97. 寻找重复数 (287. Find the Duplicate Number)
思路：看作链表找环入口（Floyd 判圈）。
int findDuplicate(vector<int>& nums) {
int slow = nums[0], fast = nums[0];
do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast);
slow = nums[0];
while (slow != fast) { slow = nums[slow]; fast = nums[fast]; }
return slow;
}
十七、补充——Hot 100 剩余题目
98. 和为 K 的子数组 (560) — 已在前文完成
99. 最短无序连续子数组 (581. Shortest Unsorted Continuous Subarray)
int findUnsortedSubarray(vector<int>& nums) {
int n = nums.size(), l = -1, r = -2, mx = nums[0], mn = nums[n-1];
for (int i = 1; i < n; ++i) {
mx = max(mx, nums[i]);
if (nums[i] < mx) r = i;
}
for (int i = n - 2; i >= 0; --i) {
mn = min(mn, nums[i]);
if (nums[i] > mn) l = i;
}
return r - l + 1;
}
100. 回文子串 (647. Palindromic Substrings)
int countSubstrings(string s) {
int n = s.size(), ans = 0;
for (int i = 0; i < n; ++i) {
for (int d : {0, 1}) {
int l = i, r = i + d;
while (l >= 0 && r < n && s[l] == s[r]) { l--; r++; ans++; }
}
}
return ans;
}
附：分类索引
| 类别 | 题目编号 |
|---|---|
| 哈希 | 1, 49, 128 |
| 双指针 | 283, 11, 15, 42 |
| 滑动窗口 | 3, 438, 560 |
| 数组 | 53, 56, 189, 238, 41 |
| 矩阵 | 73, 54, 48, 240 |
| 链表 | 160, 206, 234, 141, 142, 21, 2, 19, 24, 25, 138, 148, 23, 146 |
| 二叉树 | 94, 104, 226, 101, 543, 102, 108, 98, 230, 199, 114, 105, 437, 236, 124 |
| 图论 | 200, 994, 207, 208 |
| 回溯 | 46, 78, 17, 39, 22, 79, 131, 51 |
| 二分 | 33, 34, 74, 153, 4 |
| 栈 | 20, 155, 394, 739, 84 |
| 堆 | 215, 347, 295 |
| 贪心 | 121, 55, 45, 763 |
| 一维 DP | 70, 118, 198, 279, 322, 139, 300, 152, 416, 32 |
| 多维 DP | 62, 64, 5, 1143, 72 |
| 技巧 | 136, 169, 75, 31, 287, 581, 647 |
代码均可在 LeetCode 环境直接运行，ListNode、TreeNode 等结构体按 LeetCode 默认定义。
更多推荐
5
0- 0
已为社区贡献1条内容
所有评论(0)