随笔
Leetcode_Hot100_备战秋招刷题计划
为备战秋招，决定把LeetCode的Hot100刷一遍，目前处于刷题的第一阶段，主要是先刷一些性价比高的题。这里整理了适合理解的面试版本，供自己学习使用。
一、哈希表
1. 两数之和（简单）（短）
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); i++) {
auto it = mp.find(target - nums[i]);
if (it != mp.end()) return {it->second, i};
mp[nums[i]] = i;
}
return {};
}
记忆点：一次遍历，先查再存。
2. 字母异位词分组（中等）（短）
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;
}
记忆点：排序后的字符串作为 key。
3. 最长连续序列（中等）（短）
int longestConsecutive(vector<int>& nums) {
unordered_set<int> st(nums.begin(), nums.end());
int res = 0;
for (int x : st) {
if (st.count(x - 1)) continue;
int y = x;
while (st.count(y + 1)) y++;
res = max(res, y - x + 1);
}
return res;
}
记忆点：只从序列起点开始数。
二、双指针
4. 移动零（简单）（短）
void moveZeroes(vector<int>& nums) {
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (nums[fast]) swap(nums[slow++], nums[fast]);
}
}
记忆点：快慢指针，非零就交换。
5. 盛最多水的容器（中等）（短）
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1, res = 0;
while (l < r) {
res = max(res, min(height[l], height[r]) * (r - l));
if (height[l] < height[r]) l++; else r--;
}
return res;
}
记忆点：移动矮的那一边。
6. 三数之和（中等）（长）
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 && nums[i] == nums[i-1]) continue;
int l = i + 1, r = n - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum < 0) l++;
else if (sum > 0) r--;
else {
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--;
}
}
}
return res;
}
记忆点：排序 + 固定一个数 + 双指针 + 去重。
7. 接雨水（困难）（短）
int trap(vector<int>& height) {
int l = 0, r = height.size() - 1;
int leftMax = 0, rightMax = 0, res = 0;
while (l < r) {
leftMax = max(leftMax, height[l]);
rightMax = max(rightMax, height[r]);
if (leftMax < rightMax) res += leftMax - height[l++];
else res += rightMax - height[r--];
}
return res;
}
记忆点：左右指针，矮的一侧结算。
三、滑动窗口
8. 无重复字符的最长子串（中等）（短）
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> mp;
int l = 0, res = 0;
for (int r = 0; r < s.size(); r++) {
if (mp.count(s[r])) l = max(l, mp[s[r]] + 1);
mp[s[r]] = r;
res = max(res, r - l + 1);
}
return res;
}
记忆点：窗口左边界取 max。
9. 找到字符串中所有字母异位词（中等）（短）
vector<int> findAnagrams(string s, string p) {
vector<int> res, need(26), win(26);
for (char c : p) need[c - 'a']++;
int l = 0;
for (int r = 0; r < s.size(); r++) {
win[s[r] - 'a']++;
if (r - l + 1 > p.size()) win[s[l++] - 'a']--;
if (win == need) res.push_back(l);
}
return res;
}
记忆点：固定窗口长度，数组比对。
子串
10. 和为 K 的子数组（中等）（短）
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp{{0, 1}};
int sum = 0, res = 0;
for (int x : nums) {
sum += x;
if (mp.count(sum - k)) res += mp[sum - k];
mp[sum]++;
}
return res;
}
记忆点：前缀和 + 哈希，初始化 {0,1}。
11. 滑动窗口最大值（困难）（短）
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq;
vector<int> res;
for (int i = 0; i < nums.size(); i++) {
while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
dq.push_back(i);
if (dq.front() <= i - k) dq.pop_front();
if (i >= k - 1) res.push_back(nums[dq.front()]);
}
return res;
}
记忆点：单调队列，存下标。
12. 最小覆盖子串（困难）（跳过）
四、普通数组
13. 最大子数组和（中等）（短）
int maxSubArray(vector<int>& nums) {
int res = nums[0], cur = nums[0];
for (int i = 1; i < nums.size(); i++) {
cur = max(nums[i], cur + nums[i]);
res = max(res, cur);
}
return res;
}
记忆点：cur 以 i 结尾最大，断了重开。
14. 合并区间（中等）（短）
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
for (auto& it : intervals) {
if (res.empty() || res.back()[1] < it[0]) res.push_back(it);
else res.back()[1] = max(res.back()[1], it[1]);
}
return res;
}
记忆点：排序后，能合就合。
15. 轮转数组（中等）（跳过）
16. 除自身以外数组的乘积（中等）（短）
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, 1);
for (int i = 1; i < n; i++) res[i] = res[i-1] * nums[i-1];
int right = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= right;
right *= nums[i];
}
return res;
}
记忆点：左前缀，右累乘。
17. 缺失的第一个正数（困难）（跳过）
五、矩阵
18. 矩阵置零（中等）（跳过）
19. 螺旋矩阵（中等）（跳过）
20. 旋转图像（中等）（短）
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 (int i = 0; i < n; i++)
reverse(matrix[i].begin(), matrix[i].end());
}
记忆点：转置 + 每行反转。
21. 搜索二维矩阵 II（中等）（短）
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) j--;
else i++;
}
return false;
}
记忆点：右上角，大小走。
六、链表
22. 相交链表（简单）（短）
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *a = headA, *b = headB;
while (a != b) {
a = a ? a->next : headB;
b = b ? b->next : headA;
}
return a;
}
记忆点：走完自己的路，去走对方的路。
23. 反转链表（简单）（短）
ListNode* reverseList(ListNode* head) {
ListNode *prev = nullptr, *cur = head;
while (cur) {
ListNode* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
记忆点：三指针迭代。
24. 回文链表（简单）（短）
bool isPalindrome(ListNode* head) {
vector<int> vals;
while (head) { vals.push_back(head->val); head = head->next; }
for (int i = 0, j = vals.size() - 1; i < j; i++, j--)
if (vals[i] != vals[j]) return false;
return true;
}
记忆点：复制到数组，双指针。
25. 环形链表（简单）（短）
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;
}
记忆点：快慢指针必相遇。
26. 环形链表 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;
}
记忆点：相遇后，一个从头走，一个从相遇点走。
27. 合并两个有序链表（简单）（短）
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy, *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;
}
记忆点：虚拟头节点，尾插。
28. 两数相加（中等）（短）
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy, *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;
}
记忆点：虚拟头，进位。
29. 删除链表的倒数第 N 个结点（中等）（短）
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0, head), *fast = &dummy, *slow = &dummy;
for (int i = 0; i <= n; i++) fast = fast->next;
while (fast) { fast = fast->next; slow = slow->next; }
slow->next = slow->next->next;
return dummy.next;
}
记忆点：哑结点，快先走 n+1。
30. 两两交换链表中的节点（中等）（跳过）
31. K 个一组翻转链表（困难）（跳过）
32. 随机链表的复制（中等）（跳过）
33. 排序链表（中等）（跳过）
34. 合并 K 个升序链表（困难）（跳过）
35. LRU 缓存（中等）（长）
class LRUCache {
int cap;
list<pair<int,int>> cache;
unordered_map<int, list<pair<int,int>>::iterator> mp;
public:
LRUCache(int capacity) : cap(capacity) {}
int get(int key) {
if (!mp.count(key)) return -1;
cache.splice(cache.begin(), cache, mp[key]);
return mp[key]->second;
}
void put(int key, int value) {
if (mp.count(key)) {
mp[key]->second = value;
cache.splice(cache.begin(), cache, mp[key]);
return;
}
if (cache.size() == cap) {
mp.erase(cache.back().first);
cache.pop_back();
}
cache.push_front({key, value});
mp[key] = cache.begin();
}
};
记忆点：list + map，splice 提到头。
七、二叉树
36. 二叉树的中序遍历（简单）（短）
void inorder(TreeNode* root, vector<int>& res) {
if (!root) return;
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
记忆点：左 → 根 → 右。
37. 二叉树的最大深度（简单）（短）
int maxDepth(TreeNode* root) {
if (!root) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
记忆点：递归取 max。
38. 翻转二叉树（简单）（短）
TreeNode* invertTree(TreeNode* root) {
if (!root) return nullptr;
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
记忆点：交换左右，递归。
39. 对称二叉树（简单）（短）
bool check(TreeNode* l, TreeNode* r) {
if (!l && !r) return true;
if (!l || !r) return false;
return l->val == r->val && check(l->left, r->right) && check(l->right, r->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
记忆点：左右子树互相比较。
40. 二叉树的直径（简单）（短）
int res = 0;
int dfs(TreeNode* root) {
if (!root) return 0;
int l = dfs(root->left), r = dfs(root->right);
res = max(res, l + r);
return 1 + max(l, r);
}
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return res;
}
记忆点：后序，更新 l+r。
41. 二叉树的层序遍历（中等）（长）
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> res;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
vector<int> level;
for (int i = q.size(); i > 0; i--) {
TreeNode* cur = q.front(); q.pop();
level.push_back(cur->val);
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
res.push_back(level);
}
return res;
}
记忆点：队列，按层 size 循环。
42. 将有序数组转换为二叉搜索树（简单）（短）
TreeNode* build(vector<int>& nums, int l, int r) {
if (l > r) return nullptr;
int mid = l + (r - l) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = build(nums, l, mid - 1);
root->right = build(nums, mid + 1, r);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, nums.size() - 1);
}
记忆点：中点当根，递归。
43. 验证二叉搜索树（中等）（短）
bool check(TreeNode* root, long long low, long long high) {
if (!root) return true;
if (root->val <= low || root->val >= high) return false;
return check(root->left, low, root->val) && check(root->right, root->val, high);
}
bool isValidBST(TreeNode* root) {
return check(root, LLONG_MIN, LLONG_MAX);
}
记忆点：上下界，long long。
44. 二叉搜索树中第 K 小的元素（中等）（跳过）
45. 二叉树的右视图（中等）（跳过）
46. 二叉树展开为链表（中等）（跳过）
47. 从前序与中序遍历序列构造二叉树（中等）（跳过）
48. 路径总和 III（中等）（跳过）
49. 二叉树的最近公共祖先（中等）（短）
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* l = lowestCommonAncestor(root->left, p, q);
TreeNode* r = lowestCommonAncestor(root->right, p, q);
if (l && r) return root;
return l ? l : r;
}
记忆点：左右都找到就返回 root。
50. 二叉树中的最大路径和（困难）（跳过）
八、图
51. 岛屿数量（中等）（短）
void dfs(vector<vector<char>>& g, int i, int j) {
if (i < 0 || i >= g.size() || j < 0 || j >= g[0].size() || g[i][j] != '1') return;
g[i][j] = '0';
dfs(g, i + 1, j);
dfs(g, i - 1, j);
dfs(g, i, j + 1);
dfs(g, i, j - 1);
}
int numIslands(vector<vector<char>>& grid) {
int res = 0;
for (int i = 0; i < grid.size(); i++)
for (int j = 0; j < grid[0].size(); j++)
if (grid[i][j] == '1') { res++; dfs(grid, i, j); }
return res;
}
记忆点：遇 1 计数，DFS 淹掉。
52. 腐烂的橘子（中等）（跳过）
53. 课程表（中等）（跳过）
54. 实现 Trie（前缀树）（中等）（特长）
class Trie {
Trie* next[26] = {};
bool end = false;
public:
void insert(string word) {
Trie* node = this;
for (char c : word) {
if (!node->next[c - 'a']) node->next[c - 'a'] = new Trie();
node = node->next[c - 'a'];
}
node->end = true;
}
bool search(string word) {
Trie* node = this;
for (char c : word) {
if (!node->next[c - 'a']) return false;
node = node->next[c - 'a'];
}
return node->end;
}
bool startsWith(string prefix) {
Trie* node = this;
for (char c : prefix) {
if (!node->next[c - 'a']) return false;
node = node->next[c - 'a'];
}
return true;
}
};
记忆点：26 叉树，end 标记。
九、回溯
55. 全排列（中等）（长）
void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
if (path.size() == nums.size()) { res.push_back(path); return; }
for (int i = 0; i < nums.size(); i++) {
if (used[i]) continue;
used[i] = true;
path.push_back(nums[i]);
backtrack(nums, used, path, res);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;
vector<bool> used(nums.size());
backtrack(nums, used, path, res);
return res;
}
记忆点：used 数组 + 路径。
56. 子集（中等）（短）
void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
res.push_back(path);
for (int i = start; i < nums.size(); i++) {
path.push_back(nums[i]);
backtrack(nums, i + 1, path, res);
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;
backtrack(nums, 0, path, res);
return res;
}
记忆点：每个节点都收割，start 保证不重复。
57. 电话号码的字母组合（中等）（长）
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
vector<string> mp = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> res;
string path;
function<void(int)> dfs = [&](int i) {
if (i == digits.size()) { res.push_back(path); return; }
for (char c : mp[digits[i] - '0']) {
path.push_back(c);
dfs(i + 1);
path.pop_back();
}
};
dfs(0);
return res;
}
记忆点：数字映射，回溯。
58. 组合总和（中等）（跳过）
59. 括号生成（中等）（跳过）
60. 单词搜索（中等）（跳过）
61. 分割回文串（中等）（跳过）
62. N 皇后（困难）（跳过）
十、二分查找
63. 搜索插入位置（简单）（短）
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size();
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) l = mid + 1;
else r = mid;
}
return l;
}
记忆点：找第一个 >= target。
64. 搜索二维矩阵（中等）（跳过）
65. 在排序数组中查找元素的第一个和最后一个位置（中等）（短）
vector<int> searchRange(vector<int>& nums, int target) {
int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
int r = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
if (l == nums.size() || nums[l] != target) return {-1, -1};
return {l, r};
}
记忆点：lower/upper bound。
66. 搜索旋转排序数组（中等）（短）
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;
}
记忆点：判断哪边有序。
67. 寻找旋转排序数组中的最小值（中等）（跳过）
68. 寻找两个正序数组的中位数（困难）（跳过）
十一、栈
69. 有效的括号（简单）（短）
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();
}
记忆点：左入栈，右匹配。
70. 最小栈（中等）（短）
class MinStack {
stack<int> st, minSt;
public:
void push(int val) {
st.push(val);
minSt.push(minSt.empty() ? val : min(val, minSt.top()));
}
void pop() {
st.pop();
minSt.pop();
}
int top() { return st.top(); }
int getMin() { return minSt.top(); }
};
记忆点：辅助栈同步存最小值。
71. 字符串解码（中等）（跳过）
72. 每日温度（中等）（短）
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> res(n);
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
int j = st.top(); st.pop();
res[j] = i - j;
}
st.push(i);
}
return res;
}
记忆点：单调递减栈，存下标。
73. 柱状图中最大的矩形（困难）（跳过）
十二、堆
74. 数组中的第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();
}
记忆点：小顶堆，保持 k 个。
75. 前 K 个高频元素（中等）（短）
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
for (int x : nums) cnt[x]++;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
for (auto& [x, c] : cnt) {
pq.push({c, x});
if (pq.size() > k) pq.pop();
}
vector<int> res;
while (!pq.empty()) {
res.push_back(pq.top().second);
pq.pop();
}
return res;
}
记忆点：哈希计数 + 小顶堆。
76. 数据流的中位数（困难）（跳过）
十三、贪心
77. 买卖股票的最佳时机（简单）（短）
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX, res = 0;
for (int p : prices) {
minPrice = min(minPrice, p);
res = max(res, p - minPrice);
}
return res;
}
记忆点：维护最低价，算利润。
78. 跳跃游戏（中等）（短）
bool canJump(vector<int>& nums) {
int reach = 0;
for (int i = 0; i < nums.size(); i++) {
if (i > reach) return false;
reach = max(reach, i + nums[i]);
}
return true;
}
记忆点：维护最远可达。
79. 跳跃游戏 II（中等）（跳过）
80. 划分字母区间（中等）（跳过）
十四、动态规划
81. 爬楼梯（简单）（短）
int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2;
for (int i = 3; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}
记忆点：斐波那契，滚动变量。
82. 杨辉三角（简单）（跳过）
83. 打家劫舍（中等）（短）
int rob(vector<int>& nums) {
int prev = 0, cur = 0;
for (int x : nums) {
int tmp = max(cur, prev + x);
prev = cur;
cur = tmp;
}
return cur;
}
记忆点：抢 vs 不抢，滚动。
84. 完全平方数（中等）（跳过）
85. 零钱兑换（中等）（短）
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];
}
记忆点：完全背包，求最小。
86. 单词拆分（中等）（短）
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> st(wordDict.begin(), wordDict.end());
vector<bool> dp(s.size() + 1);
dp[0] = true;
for (int i = 1; i <= s.size(); i++)
for (int j = 0; j < i; j++)
if (dp[j] && st.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
return dp[s.size()];
}
记忆点：dp[i] 前 i 个能否拆。
87. 最长递增子序列（中等）（短）
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();
}
记忆点：tails 数组 + lower_bound。
88. 乘积最大子数组（中等）（短）
int maxProduct(vector<int>& nums) {
int res = nums[0], imax = nums[0], imin = nums[0];
for (int i = 1; i < nums.size(); i++) {
if (nums[i] < 0) swap(imax, imin);
imax = max(nums[i], imax * nums[i]);
imin = min(nums[i], imin * nums[i]);
res = max(res, imax);
}
return res;
}
记忆点：同时维护最大最小，负号交换。
89. 分割等和子集（中等）（短）
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);
dp[0] = true;
for (int x : nums)
for (int j = target; j >= x; j--)
dp[j] = dp[j] || dp[j - x];
return dp[target];
}
记忆点：01 背包，倒序。
90. 最长有效括号（困难）（跳过）
十五、多维动态规划
91. 不同路径（中等）（短）
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];
}
记忆点：一维滚动，dp[j] += dp[j-1]。
92. 最小路径和（中等）（短）
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<int> dp(n, 0);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) dp[j] = grid[i][j];
else if (i == 0) dp[j] = dp[j - 1] + grid[i][j];
else if (j == 0) dp[j] = dp[j] + grid[i][j];
else dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
}
return dp[n - 1];
}
记忆点：一维，左和上取小。
93. 最长回文子串（中等）（长）
string longestPalindrome(string s) {
int start = 0, maxLen = 1;
auto expand = [&](int l, int r) {
while (l >= 0 && r < s.size() && s[l] == s[r]) {
l--; r++;
}
if (r - l - 1 > maxLen) {
maxLen = r - l - 1;
start = l + 1;
}
};
for (int i = 0; i < s.size(); i++) {
expand(i, i);
expand(i, i + 1);
}
return s.substr(start, maxLen);
}
记忆点：中心扩展，奇偶各一次。
94. 最长公共子序列（中等）（短）
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (text1[i - 1] == text2[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];
}
记忆点：相等左上 +1，否则上左取大。
95. 编辑距离（中等）（跳过）
十六、技巧
96. 只出现一次的数字（简单）（短）
int singleNumber(vector<int>& nums) {
int res = 0;
for (int x : nums) res ^= x;
return res;
}
记忆点：异或。
97. 多数元素（简单）（短）
int majorityElement(vector<int>& nums) {
int cand = 0, cnt = 0;
for (int x : nums) {
if (cnt == 0) cand = x;
cnt += (x == cand) ? 1 : -1;
}
return cand;
}
记忆点：摩尔投票。
98. 颜色分类（中等）（短）
void sortColors(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
for (int i = 0; i <= r; i++) {
if (nums[i] == 0) swap(nums[l++], nums[i]);
else if (nums[i] == 2) swap(nums[r--], nums[i--]);
}
}
记忆点：三指针，0 左换，2 右换。