1. 基本操作：增删查改 遍历方式：迭代递归 穷举：无遗漏、无冗余
2. 回溯算法
2.1. DFS
2.2. BFS
2.2.1. 层序遍历
2.2.1.1. // 层序遍历 void broadTraverse(TreeNode* root) { if (root == nullptr) return; queque<TreeNode *> q; q.push(root); // 深度 while (!q.empty()) { int sz = q.size(); for (int i = 0; i < sz; ++i) { TreeNode* cur = q.front(); // 拿出当前节点 q.pop(); // 将下层放进来 if (cur->left != nullptr) { q.push(cur->left); } if (cur->right != nullptr) { q.push(cur->right); } } } }
2.3. 排列/组合/子集
2.3.1. 经典结构：全排列问题
2.3.1.1. // 回溯 1. 路径 2. 选择列表 3. 结束条件 vector<vector<int>> res; // 答案列表 void backwards(vector<int> nums, vector<int>& track, vector<bool>& used) { if (track.size() == nums.size()) { res.push_back(track); // 结束动作 return; } // 遍历每一个元素 for (int i = 0; i < used.size(); ++i) { if (used[i]) { continue; // 选到没有用过的 } // 做选择，前序遍历 track.push_back(nums[i]); used[i] = true; backwards(nums, track, used); // 做撤销，后序遍历 track.pop_back(); used[i] = false; } } vector<vector<int>> permute(vector<int>& nums) { // 记录【track】 vector<int> track; // 维护【选择列表】 vector<bool> used(nums.size(), false); backwards(nums, track, used); return res; }
2.3.2. 1、元素无重不可复选
2.3.2.1. 组合/子集
2.3.2.1.1. void backtrack(vector<int>& nums, int start) { // 回溯算法标准框架 for (int i = start; i < nums.size(); i++) { // 做选择 track.push_back(nums[i]); // 注意参数 backtrack(nums, i + 1); // 撤销选择 track.pop_back(); } }
2.3.2.2. 排列
2.3.2.2.1. void backtrack(vector<int>& nums) { for (int i = 0; i < nums.size(); i++) { // 剪枝逻辑 if (used[i]) { continue; } // 做选择 used[i] = true; track.push_back(nums[i]); backtrack(nums); // 撤销选择 track.pop_back(); used[i] = false; } }
2.3.3. 2、元素可重不可复选
2.3.3.1. 组合/子集
2.3.3.1.1. sort(nums.begin(), nums.end()); /* 组合/子集问题回溯算法框架 */ void backtrack(vector<int>& nums, int start) { //回溯算法标准框架 for (int i = start; i < nums.size(); i++) { // 剪枝逻辑，跳过值相同的相邻树枝 if (i > start && nums[i] == nums[i - 1]) { continue; } // 做选择 track.push_back(nums[i]); // 注意参数 backtrack(nums, i + 1); // 撤销选择 track.pop_back(); } }
2.3.3.2. 排列
2.3.3.2.1. sort(nums.begin(), nums.end()); /* 排列问题回溯算法框架 */ void backtrack(vector<int>& nums, vector<bool>& used) { for (int i = 0; i < nums.size(); i++) { // 剪枝逻辑 if (used[i]) { continue; } // 剪枝逻辑，固定相同的元素在排列中的相对位置 if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { continue; } // 做选择 used[i] = true; track.push_back(nums[i]); backtrack(nums, used); // 撤销选择 track.pop_back(); used[i] = false; } }
2.3.4. 3、元素无重可复选
2.3.4.1. 组合/子集
2.3.4.1.1. /* 组合/子集问题回溯算法框架 */ void backtrack(vector<int>& nums, int start, deque<int>& track) { // 回溯算法标准框架 for (int i = start; i < nums.size(); i++) { // 做选择 track.push_back(nums[i]); // 注意参数 backtrack(nums, i, track); // 撤销选择 track.pop_back(); } }
2.3.4.2. 排列
2.3.4.2.1. /* 排列问题回溯算法框架 */ void backtrack(vector<int>& nums, deque<int>& track) { for (int i = 0; i < nums.size(); i++) { // 做选择 track.push_back(nums[i]); backtrack(nums, track); // 撤销选择 track.pop_back(); } }
2.4. 经典结构：N皇后
2.4.1. // 1. 路径 2. 选择列表 3. 终止条件 vector<vector<string>> ans; // 记录答案 void backwards(vector<string> board, int row) { int n = board.size(); // 3. 终止条件 if (row >= board.size()) { ans.push_back(board); return; } // 做选择，选择列表是该row的全部元素 for (int i = 0; i < n; ++i) { if (isLegal(board, row, i)) { board[row][i] = 'Q'; // 合法就放Q // row++; // 到下一行去 backwards(board, row+1); // 撤销选择 // row--; board[row][i] = '.'; } } } // isLegal函数，看当前格子是否合理 bool isLegal(vector<string> board, int row, int col) { // a. 看上面的格子合理与否 for (int i = 0; i <= row; ++i) { if (board[i][col] == 'Q') return false; } // b. 左上角所有格子合理与否 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) { if (board[i][j] == 'Q') return false; } // c. 右上角所有格子合理与否 for (int i = row - 1, j = col + 1; i >= 0 && j < board.size(); --i, ++j) { if (board[i][j] == 'Q') return false; } // 都合理 return true; } vector<vector<string>> solveNQueens(int n) { // 2. 选择列表 vector<string> board(n, string(n, '.')); backwards(board, 0); return ans; }
3. dp
3.1. 状态转移方程
3.2. 最优子结构
3.3. 重叠子问题
3.4. dp框架
3.4.1. 确定【base case】
3.4.2. 确定【状态】
3.4.3. 确定【选择】
3.5. dp套路框架
3.5.1. 零钱兑换
3.5.1.1. class Solution { public: int coinChange(vector<int>& coins, int amount) { return dp(coins, amount); } int dp(vector<int> coins, int amount) { // base case if (amount == 0) return 0; if (amount < 0) return -1; int res = INT_MAX; for (int coin : coins) { // 计算子问题的结果，最优子问题 int subProblem = dp(coins, amount - coin); // 子问题无解则跳过 if (subProblem == -1) continue; // 保优 res = min(res, subProblem + 1); } return res == INT_MAX ? -1 : res; } };
4. 数学算法
5. 基本数据结构
5.1. 栈
5.1.1. 先进后出
5.2. 队列
5.2.1. 先进先出
5.3. 优先队列
5.3.1. 大根堆
5.3.1.1. 首元素总是最大的
5.3.2. 小根堆
5.3.2.1. 首元素总是最小的
5.4. set集合
5.4.1. set
5.4.1.1. 不重复、从小到大
5.4.2. multiset
5.4.2.1. 可重复、从小到大
5.4.3. unordered_set
5.4.3.1. 不可重复、无序
5.5. map集合
5.5.1. 键值对
5.5.1.1. unordered_map<char, int> map = { {'I' , 1}, {'V' , 5}, {'X' , 10}, {'L' , 50}, {'C' , 100}, {'D' , 500}, {'M' , 1000}, }; int romanToInt(string s) { int ans = 0; for (int i = 0; i < s.length(); ++i) { int value = map[s[i]]; if (i < s.length() - 1 && map[s[i + 1]] > value) { ans -= value; } else { ans += value; } } return ans; }
5.6. string
5.6.1. 操作字符串
5.7. pair（二元组）
5.7.1. 坐标
6. 迭代/递归
6.1. 迭代：一直深入问一件事情
6.2. 递归：深度优先
7. 数组
7.1. 双指针
7.1.1. 左右指针
7.1.1.1. 两端向中间收缩的双指针
7.1.1.1.1. 二分搜索
7.1.1.1.2. 反转数组
7.1.1.1.3. 回文串判断
7.1.1.1.4. vector<int> twoSum(vector<int>& numbers, int target) { int left = 0, right = numbers.size() - 1; vector<int> ans(2); while (left < right) { // 可不可以重复 int sumTarget = numbers[left] + numbers[right]; if (sumTarget == target) { ans[0] = left + 1; ans[1] = right + 1; return ans; } else if (sumTarget < target){ left++; } else if (sumTarget > target) { right--; } } return ans; }
7.1.1.2. 中间向两端扩散的双指针
7.1.1.2.1. 最长回文子串
7.1.2. 快慢指针（同向）
7.1.2.1. 滑动窗口
7.1.2.2. 数组
7.1.2.2.1. int removeElement(vector<int>& nums, int val) { int fast = 0, slow = 0; for (int i = 0; i < nums.size(); ++i) { if (nums[fast] != val) { nums[slow] = nums[fast]; slow++; } fast++; } return slow; }
7.1.3. 前缀
7.1.4. 差分数组
8. 链表
8.1. 双指针
8.1.1. ListNode* deleteDuplicates(ListNode* head) { if (head == NULL) return NULL; ListNode *slow = head, *fast = head; while (fast != NULL) { if (fast->val != slow->val) { slow->next = fast; slow = slow->next; } fast = fast->next; } slow->next = NULL; return head; }
8.1.2. 合并两个有序链表
8.1.2.1. ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* dummy = new ListNode(-1), *p = dummy; while (list1 != NULL && list2 != NULL) { if (list1->val > list2->val) { p->next = list2; list2 = list2->next; } else { p->next = list1; list1 = list1->next; } p = p->next; } if (list1 != NULL) { p->next = list1; } if (list2 != NULL) { p->next = list2; } return dummy->next; }
8.1.3. 链表的分解
8.1.3.1. ListNode* partition(ListNode* head, int x) { ListNode *dummy1 = new ListNode(-1), *p1 = dummy1; ListNode *dummy2 = new ListNode(-1), *p2 = dummy2; ListNode *p = head; // 遍历链表 while (p != NULL) { if (p->val < x) { p1->next = p; p1 = p1->next; } else { p2->next = p; p2 = p2->next; } // 断开 ListNode *temp = p->next; p->next = NULL; p = temp; } // 合并链表 p1->next = dummy2->next; return dummy1->next; }
8.1.4. 合并k个有序链表
8.1.4.1. struct minStack { int val; ListNode *thptr; bool operator < (const minStack &rhs) const { return val > rhs.val; } }; priority_queue<minStack> q; ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode* dummy = new ListNode(-1), *p = dummy; // ans // 1. 创建小根堆，根据val排序 for (auto head : lists) { if (head) q.push({head->val, head}); } // 2. 每次都取出top，然后pop()，把下一个再push到第一个 while (!q.empty()) { auto f = q.top(); q.pop(); p->next = f.thptr; p = p->next; if (f.thptr->next) q.push({f.thptr->next->val, f.thptr->next}); } return dummy->next; }
8.1.5. 寻找单链表的倒数第k个节点
8.1.5.1. ListNode* trainingPlan(ListNode* head, int cnt) { ListNode *pfast = head, *pslow = head; for (int i = 0; i < cnt; ++i) { pfast = pfast->next; } while (pfast != nullptr) { pfast = pfast->next; pslow = pslow->next; } return pslow; }
8.1.6. 删除单链表的倒数第k个节点
8.1.6.1. ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *fast = head; ListNode *dummy = new ListNode(-1), *slow = dummy; // 用dummy维护链表，用slow操作链表 slow->next = head; for (int i = 0; i < n; ++i) { fast = fast->next; } while (fast != nullptr) { fast = fast->next; slow = slow->next; } // 此时slow在的位置是n-1 slow->next = slow->next->next; return dummy->next; }
8.1.7. 寻找单链表的中点
8.1.7.1. ListNode* middleNode(ListNode* head) { ListNode *fast = head, *slow = head; while (fast != nullptr && fast->next != nullptr) { fast = fast->next->next; slow = slow->next; } return slow; }
8.1.8. 判断单链表是否包含环并找出环起点
8.1.8.1. ListNode *detectCycle(ListNode *head) { ListNode *fast = head, *slow = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) { break; } } // 无环 if (fast == NULL || fast->next == NULL) { return NULL; } slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; }
8.1.9. 判断两个单链表是否相交并找出交点
8.1.9.1. ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *pA = headA, *pB = headB; while (pA != pB) { // 遍历完A链表，再遍历B if (pA != NULL) { pA = pA->next; } else { pA = headB; } // 遍历完B链表，在遍历A if (pB != NULL) { pB = pB->next; } else { pB = headA; } } return pA; // 要不是找到了交点，要不都是NULL }
9. 二叉树
9.1. 回溯算法核心思路
9.1.1. DFS深度优先遍历
9.1.2. 1. 路径（答案） 2. 选择列表：当前可以做的选择 3. 结束条件：达到决策树底层，无法再做选择的条件 决策树：由每次的决策衍生出来的树结构，每一条由root →bottom的路径都是一个解
9.1.3. BFS广度优先遍历
9.2. 动态规划核心思路
9.3. 前序/中序/后序遍历
9.4. 二叉搜索树（BST）
9.4.1. 左子树都比当前节点小，右子树都比当前节点大；
9.4.2. 中序遍历结果有序（升序）
9.5. 题目
9.5.1. 相同的树
9.5.1.1. bool isSameTree(TreeNode* p, TreeNode* q) { // 都为null，true if (p == nullptr && q == nullptr) return true; // 不同时为null，结构不同，false else if (p == nullptr || q == nullptr) return false; // 不为null，但是值不相同，false else if (p->val != q->val) return false; // 值相同，看子节点是否为空，做同样的上述操作 else { return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } }
9.5.2. 二叉树的直径
9.5.2.1. int diameterMax = 0; int traverse(TreeNode *root) { if (root == nullptr) return 0; int leftMax = traverse(root->left); int rightMax = traverse(root->right); // 后序遍历，因为要知道了所有子节点的深度了，才能算直径 diameterMax = max(diameterMax, leftMax + rightMax); return 1 + max(leftMax, rightMax); } int diameterOfBinaryTree(TreeNode* root) { traverse(root); return diameterMax; }
9.5.3. 二叉树的最大深度
9.5.3.1. int ans = 0; int depth = 0; void traverse(TreeNode* root) { if (root == nullptr) return; // 记录当前层 depth++; ans = max(depth, ans); traverse(root->left); traverse(root->right); depth--; } int maxDepth(TreeNode* root) { traverse(root); return ans; }
9.5.4. 前序遍历构造BST
9.5.4.1. int index = 0; // 遍历计数 vector<int> tempPreorder; int len; TreeNode* dfs(int lowerBound, int upperBound) { if (index == len) return nullptr; // 遍历完毕 // 前序遍历 int cur = tempPreorder[index]; // 在[left..right] 构建二叉树 if (cur < lowerBound || cur > upperBound) { return nullptr; } index++; TreeNode* root = new TreeNode(cur); root->left = dfs(lowerBound, cur); root->right = dfs(cur, upperBound); return root; } TreeNode* bstFromPreorder(vector<int>& preorder) { tempPreorder = preorder; len = tempPreorder.size(); return dfs(INT_MIN, INT_MAX); }
9.5.5. 对称二叉树
9.5.5.1. bool check(TreeNode* q, TreeNode* p) { // 都为空，return true; if (!q && !p) return true; // 不同时为空，return fasle； if (!q || !p) return false; // 都不为空，比较值 return q->val == p->val && check(q->left, p->right) && check(q->right, p->left); } bool isSymmetric(TreeNode* root) { return check(root, root); }