1. 项目概述：一份为C++选手量身定制的算法精进地图

如果你是一名正在用C++刷LeetCode的开发者，无论是为了面试冲刺，还是为了系统性提升算法能力，你大概率都经历过这样的迷茫：题库里两千多道题，从何刷起？是跟着官方列表顺序，还是看哪个“热题100”榜单？刷完一道题，除了“AC”的短暂快感，似乎并没有形成深刻的理解和体系化的记忆。更让人头疼的是，很多题解虽然提供了答案，但背后的解题思想、代码优化技巧、以及如何将这道题的经验迁移到其他问题上，往往语焉不详。

这份笔记，正是为了解决这些问题而生。它不是简单的题目答案合集，而是一份以C++为核心实现语言，以构建完整算法知识体系为目标，经过精心排序和深度解析的刷题路线图。其核心价值在于“顺序”和“详解”。顺序，决定了你学习路径的效率，避免在知识孤岛间跳跃；详解，则确保你每刷一题，都能吃透其背后的思想、写出一段高效优雅的C++代码，并建立起与其他题目的联系。我会持续更新这份笔记，力求覆盖核心算法与数据结构，让你用最少的时间，获得最扎实的成长。

2. 刷题顺序设计的核心逻辑与路线图

盲目刷题是效率最低的学习方式。一个科学的顺序，应该符合认知规律，即由浅入深、由点及面、前后关联。我设计的这个顺序，主要基于以下几个原则：

2.1 原则一：数据结构先行，算法随后这是构建大厦的基石。你必须先熟悉“砖瓦”（数据结构）的特性，才能学会如何用它们“盖房子”（设计算法）。因此，路线会从最基础的数组、字符串、链表开始，逐步过渡到栈、队列、哈希表，再到复杂的树、图，最后是高级数据结构如堆、并查集、前缀树等。在每个数据结构模块内，再融入相关的算法思想。

2.2 原则二：同类型题目集中突破这是形成肌肉记忆和思维模式的关键。将相同解法或相同数据结构的题目放在一起连续练习，能让你快速掌握这类问题的“套路”。例如，在“链表”模块，我会把涉及虚拟头节点、快慢指针、反转链表、合并链表的题目集中讲解，让你一次吃透。

2.3 原则三：难度螺旋式上升在每个小模块内，题目难度会从Easy到Medium，偶尔穿插Hard。这保证了学习的平滑性。你不会在还没掌握基础遍历时，就去挑战复杂的树形DP。整个大路线也是从基础数据结构，到基础算法（排序、二分、双指针），再到高级算法（回溯、动规、贪心、图论）。

2.4 原则四：强调前后关联与知识迁移在讲解一道题时，我会明确指出它和之前哪道题的思想一脉相承，或者它能为后面哪类难题打下基础。例如，学会了“两数之和”（哈希表），那么“三数之和”（排序+双指针）的解法虽然不同，但你可以对比思考为何此处不用哈希表，从而加深对算法适用场景的理解。

注意：这份顺序并非LeetCode题号的顺序，也不同于任何单一的“热题”列表。它是基于我个人和众多上岸者的经验，重新组织的一个学习路径。你可以把它看作一门精心编排的“算法课程”大纲。

基于以上原则，我规划的初始核心路线图如下：

1. 第一阶段：编程基础与线性结构

   • 目标：熟悉C++ STL基础容器操作，掌握数组、字符串、链表的常见处理方法。
   • 核心题目类型：数组基本操作、字符串处理、链表增删改查、双指针技巧（快慢指针、左右指针）。

2. 第二阶段：基础数据结构与简单算法

   • 目标：掌握栈、队列、哈希表的应用，理解递归，入门二叉树。
   • 核心题目类型：栈实现表达式求值/括号匹配、队列应用、哈希表解决查找问题、二叉树遍历（递归/迭代）。

3. 第三阶段：中级算法思想

   • 目标：攻克排序、二分查找、滑动窗口、回溯算法、基础动态规划。
   • 核心题目类型：各种排序算法的应用场景、二分查找的变体、滑动窗口解决子串/子数组问题、排列组合类回溯、经典一维/二维DP问题。

4. 第四阶段：高级数据结构与复杂算法

   • 目标：掌握堆、并查集、图论算法、复杂动态规划与贪心策略。
   • 核心题目类型：堆解决TopK问题、并查集处理连通性、图的DFS/BFS及最短路径、背包问题、区间DP、贪心选择证明。

这个路线是动态的，我会在每个阶段的详解中，插入必须掌握的经典题目和具有代表性的新题。

3. C++刷题详解的核心方法论：不止于AC

刷题的目标不是提交通过，而是“掌握”。对于每一道入选的题目，我的详解笔记会包含以下几个层次，这也是你自查是否真正掌握一道题的标准：

3.1 题意理解与边界条件分析这是所有步骤的基础，却最容易被忽视。我会带你仔细审题，识别出所有可能的边界情况（空输入、单个元素、极大/极小值、负数等），并在思路分析阶段就考虑进去。例如，链表题目常需考虑头节点被修改或删除的情况，这通常引入“虚拟头节点”技巧。

3.2 多解法对比与时空复杂度分析一道题往往有多种解法。我会从最直观的暴力法开始，分析其缺点，然后逐步优化，引出更高效的算法。对于每一种解法，都会明确给出时间复杂度和空间复杂度，并解释为什么。这能训练你评估算法优劣的能力。

• 示例：对于“两数之和”，我们会对比暴力O(n²)和哈希表O(n)解法，并讨论为何哈希表在此处更优（频繁查找）。

3.3 C++实现细节与STL技巧这是本笔记的特色所在。我会提供可直接运行的C++代码，并重点讲解其中的关键点：

• 容器选择：为什么用vector而不是deque？用unordered_map还是map？
• 迭代器与索引：在遍历时，何种情况下用索引访问更安全清晰？何种情况下用迭代器或范围for循环更现代？
• 函数参数传递：何时用值传递、引用传递（&）、常量引用（const &）？这直接影响效率。
• 内存与拷贝：注意不必要的临时对象拷贝，特别是在递归或循环中。
• STL算法应用：巧妙使用sort,lower_bound,next_permutation等算法，能极大简化代码。

3.4 代码注释与可读性提供的代码将包含关键步骤的注释，说明“为什么这么做”。良好的变量命名和代码结构，本身就是面试的加分项。

3.5 关联题目与举一反三在题目最后，我会列出与之强相关的题目编号，并简要说明关联点。鼓励你立即去尝试，巩固刚学到的模式。

4. 第一阶段详解：数组、字符串与链表（实战入门）

让我们正式进入第一阶段的实战。这是培养代码感觉和掌握基础操作的关键时期。

4.1 数组篇：从简单操作到双指针思想

数组是连续的内存空间，支持随机访问。LeetCode上很多题目本质是数组操作。

• 经典入门：27. 移除元素

  • 题意：原地移除数组中所有值等于val的元素，返回新数组长度。
  • 核心解法：快慢指针（双指针）。这是必须掌握的经典范式。
  • C++详解：

    class Solution { public: int removeElement(vector<int>& nums, int val) { int slowIndex = 0; // 慢指针，指向下一个待填充的位置（即新数组的末尾） for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) { // 快指针遍历原数组 if (nums[fastIndex] != val) { // 当快指针找到不需要删除的元素时 nums[slowIndex] = nums[fastIndex]; // 将其赋值给慢指针位置 slowIndex++; // 慢指针向前移动，新数组长度+1 } // 如果等于val，快指针继续走，慢指针不动，相当于“跳过”了这个元素 } return slowIndex; // 慢指针最终的位置就是新数组的长度 } };

  • 为什么是O(n)时间复杂度：快指针遍历一次数组，每个元素只被处理一次。
  • 关联题目：26.删除有序数组中的重复项（快慢指针变体），283.移动零（本质相同）。

• 双指针进阶：977. 有序数组的平方

  • 题意：非递减顺序排序的整数数组，返回每个数字平方后，按非递减顺序排序的新数组。
  • 核心解法：数组本身有序，但平方后最大值在两端。使用左右指针向中间遍历，比较平方值，从后向前填充新数组。
  • C++实现要点：

    vector<int> sortedSquares(vector<int>& nums) { int n = nums.size(); vector<int> result(n); // 预先分配好空间，避免push_back int left = 0, right = n - 1, pos = n - 1; // pos指向结果数组当前待填充的位置（从后往前） while (left <= right) { // 注意等号，要处理最后一个元素 int leftSquare = nums[left] * nums[left]; int rightSquare = nums[right] * nums[right]; if (leftSquare > rightSquare) { result[pos--] = leftSquare; left++; } else { result[pos--] = rightSquare; right--; } } return result; }

  • 心得：对于需要反向填充或从两端向中间收敛的问题，左右指针是利器。预先分配vector大小比动态push_back在性能上更优。

4.2 字符串篇：理解不可变性与常用操作

在C++中，string是可变的，这比某些语言更方便。重点掌握子串、翻转、匹配等操作。

• 经典例题：344. 反转字符串

  • 题意：原地反转字符串，必须使用O(1)额外空间。
  • 解法：左右指针交换。
  • C++细节：使用swap函数或直接使用异或操作进行交换。注意循环条件是left < right。

    void reverseString(vector<char>& s) { for (int i = 0, j = s.size() - 1; i < j; i++, j--) { swap(s[i], s[j]); // 标准库swap // 或者手动交换: char temp = s[i]; s[i] = s[j]; s[j] = temp; } }

• 核心挑战：151. 翻转字符串里的单词

  • 题意：翻转字符串中单词的顺序，并去除多余空格。
  • 解题思路：这是一道综合题。可以分为三步：
    1. 去除多余空格：使用快慢指针原地去除首尾和中间多余空格，类似数组移除元素。
    2. 反转整个字符串。
    3. 反转每个单词：在反转后的字符串中，找到每个单词的起止位置，分别进行反转。
  • C++实现（关键函数）：

    void removeExtraSpaces(string& s) { int slow = 0; // 慢指针 for (int fast = 0; fast < s.size(); ++fast) { if (s[fast] != ' ') { // 遇到非空格就处理，即删除所有空格 if (slow != 0) s[slow++] = ' '; // 在单词前手动添加空格（第一个单词除外） while (fast < s.size() && s[fast] != ' ') { s[slow++] = s[fast++]; // 拷贝整个单词 } } } s.resize(slow); // slow的大小即为去除多余空格后的大小 }

  • 关联题目：剑指 Offer 58 - II. 左旋转字符串（局部反转+整体反转技巧）。

4.3 链表篇：掌握指针操作与虚拟头节点

链表题目是面试高频点，核心是理解指针（引用）的指向关系。建议在纸上画图分析。

• 基础操作：203. 移除链表元素

  • 题意：删除链表中所有满足node.val == val的节点。
  • 难点：头节点可能被删除。这是引入虚拟头节点（dummy node）的经典场景。
  • C++详解：

    ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead = new ListNode(0); // 创建一个虚拟头节点，其next指向真实头节点 dummyHead->next = head; ListNode* cur = dummyHead; // 当前检查的节点，从虚拟头开始 while (cur->next != nullptr) { if (cur->next->val == val) { // 找到需要删除的节点 ListNode* tmp = cur->next; // 保存待删除节点 cur->next = cur->next->next; // 跳过该节点 delete tmp; // C++需要手动释放内存（面试中需注意） } else { cur = cur->next; // 否则，当前节点向后移动 } } head = dummyHead->next; // 新的头节点可能是原来的下一个节点 delete dummyHead; // 删除虚拟头节点 return head; }

  • 重要心得：使用虚拟头节点可以统一删除逻辑，无需单独处理头节点。在C++中，操作链表时一定要注意内存管理，如果删除了节点，要用delete释放（除非题目说明不需要）。

• 快慢指针应用：142. 环形链表 II

  • 题意：判断链表是否有环，并返回环的入口节点。
  • Floyd判圈算法：这是必须掌握的数学结论。设置快指针（每次两步）和慢指针（每次一步）。
    1. 如果快指针遇到nullptr，则无环。
    2. 如果有环，快慢指针必在环内某点相遇。
    3. 此时，将其中一个指针移回链表头，然后两个指针都每次走一步，再次相遇的点即为环的入口。
  • C++代码框架：

    ListNode *detectCycle(ListNode *head) { ListNode* fast = head; ListNode* slow = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if (slow == fast) { // 相遇，有环 ListNode* index1 = head; ListNode* index2 = fast; // 或slow while (index1 != index2) { index1 = index1->next; index2 = index2->next; } return index1; // 环的入口 } } return nullptr; // 无环 }

  • 为什么可行？这涉及到数学推导。设头到入口距离为a，入口到相遇点距离为b，相遇点再到入口距离为c。第一次相遇时，慢指针走了a+b，快指针走了a+n(b+c)+b。由于快指针速度是慢指针两倍，可得a = (n-1)(b+c)+c。这个等式意味着，从head走a步，和从相遇点走c步（再绕n-1圈）会到达同一点（入口）。所以第二次相遇点就是入口。

第一阶段的核心是建立对基础数据结构的熟练度，并初步掌握双指针这一强大工具。务必做到每道题都能手写无误，并理解其所有变种。

5. 第二阶段详解：哈希表、栈、队列与二叉树基础

掌握了线性结构后，我们进入更抽象的数据结构。它们能帮你解决更复杂的问题。

5.1 哈希表：以空间换时间的利器

C++中常用unordered_set（集合）和unordered_map（映射）。其查找、插入的平均时间复杂度为O(1)。

• 经典入门：1. 两数之和

  • 题意：在数组中找出和为目标值的两个数，返回其索引。
  • 暴力法：两层循环，O(n²)。
  • 哈希表优化：在遍历数组时，对于当前元素nums[i]，我们检查target - nums[i]是否在之前遍历过的元素集合中。为了同时保存值和索引，我们使用unordered_map<int, int>，key是数值，value是对应索引。
  • C++实现：

    vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> hashmap; // value -> index for (int i = 0; i < nums.size(); ++i) { auto it = hashmap.find(target - nums[i]); if (it != hashmap.end()) { return {it->second, i}; // 找到，返回之前存的索引和当前索引 } hashmap[nums[i]] = i; // 没找到，将当前值存入哈希表 } return {}; // 题目保证有解，这里为了完整性返回空 }

  • 思考：为什么边遍历边存，而不是先全部存入？因为要避免同一个元素被使用两次。例如target=6, nums=[3]，如果先全存进去，就会找到自己。

• 哈希集合应用：202. 快乐数

  • 题意：判断一个数是否是快乐数（各位平方和最终变为1）。
  • 关键：如果不是快乐数，平方和会进入一个循环。如何检测循环？——哈希集合。
  • C++思路：计算平方和，如果等于1则返回true；如果这个和已经在集合中出现过，说明进入了循环，返回false；否则将和加入集合并继续。

    bool isHappy(int n) { unordered_set<int> seen; while (n != 1 && !seen.count(n)) { seen.insert(n); n = getNext(n); // 计算下一个平方和 } return n == 1; } int getNext(int n) { int sum = 0; while (n > 0) { int digit = n % 10; sum += digit * digit; n /= 10; } return sum; }

5.2 栈与队列：理解后进先出与先进先出

栈非常适合处理对称性、递归转迭代、路径回溯等问题。队列则用于BFS（广度优先搜索）。

• 栈的经典应用：20. 有效的括号

  • 题意：判断一个只包含括号的字符串是否有效。
  • 解法：遍历字符串，遇到左括号就压栈，遇到右括号就检查栈顶是否匹配的左括号，匹配则弹出，不匹配或栈空则无效。最后栈空才有效。
  • C++实现技巧：使用unordered_map来映射右括号到左括号，使代码更简洁。

    bool isValid(string s) { stack<char> st; unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}}; for (char ch : s) { if (pairs.count(ch)) { // 当前字符是右括号 if (st.empty() || st.top() != pairs[ch]) { return false; } st.pop(); // 匹配成功，弹出栈顶左括号 } else { // 当前字符是左括号 st.push(ch); } } return st.empty(); // 最后栈必须为空 }

• 队列与BFS入门：102. 二叉树的层序遍历

  • 题意：按层返回二叉树节点的值。
  • BFS标准模板：使用队列。将根节点入队，然后循环（队列不空时）：记录当前队列大小（即本层节点数），循环处理该大小的所有节点（出队、记录值、将其左右子节点入队）。
  • C++代码：

    vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if (!root) return result; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int levelSize = q.size(); // 关键：记录当前层的节点数 vector<int> level; for (int i = 0; i < levelSize; ++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); } result.push_back(level); } return result; }

  • 心得：levelSize的获取必须在for循环之外，因为q.size()在循环中是变化的。这是BFS层序遍历的固定写法，务必熟记。

5.3 二叉树基础：递归与迭代遍历

二叉树是理解递归和后续复杂树形DP的基础。必须熟练掌握三种深度优先遍历（前序、中序、后序）的递归和迭代写法。

• 递归遍历（以前序为例）：

  void preorder(TreeNode* root, vector<int>& res) { if (!root) return; res.push_back(root->val); // 前序：根左右 preorder(root->left, res); preorder(root->right, res); }

  递归非常直观，但需要理解函数调用栈。面试时可能会要求写迭代法。

• 迭代遍历（使用栈模拟递归）：

  • 前序迭代：由于访问顺序是“根左右”，我们可以先将根节点压栈，然后循环（栈不空）：出栈访问，然后先右后左压栈（保证出栈时是左先于右）。

    vector<int> preorderTraversal(TreeNode* root) { vector<int> result; if (!root) return result; stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); result.push_back(node->val); if (node->right) st.push(node->right); // 右先入栈 if (node->left) st.push(node->left); // 左后入栈 } return result; }

  • 中序迭代：中序是“左根右”，需要借助指针来帮助访问。思路是：指针指向当前节点，只要节点不为空就压栈并向左走（cur = cur->left）；节点为空时，弹出栈顶（此时栈顶是最左侧的节点），访问它，然后指针指向其右子树。

    vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; TreeNode* cur = root; while (cur != nullptr || !st.empty()) { if (cur != nullptr) { // 指针来访问节点，访问到最底层 st.push(cur); // 将访问的节点放进栈 cur = cur->left; // 左 } else { cur = st.top(); st.pop(); // 从栈里弹出的数据，就是要处理的数据 result.push_back(cur->val); // 中 cur = cur->right; // 右 } } return result; }

  • 后序迭代：后序是“左右根”，可以看作是“根右左”的前序遍历的逆序。所以可以按照类似前序但“先左后右”的顺序遍历，最后反转结果。

    vector<int> postorderTraversal(TreeNode* root) { vector<int> result; if (!root) return result; stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); result.push_back(node->val); if (node->left) st.push(node->left); // 相对于前序，这里顺序调换 if (node->right) st.push(node->right); } reverse(result.begin(), result.end()); // 将结果反转 return result; }

掌握二叉树的遍历是解决所有树问题的基础。很多问题，例如求深度、找路径、判断对称等，都是遍历的变体。

6. 第三阶段详解：回溯、动规与贪心算法精讲

这是算法学习的核心难点，也是面试中的重头戏。理解其思想比背诵模板更重要。

6.1 回溯算法：枚举所有可能性的艺术

回溯本质是深度优先搜索（DFS），用于解决组合、排列、分割、子集等问题。其核心是“尝试-回溯”的递归过程。

• 模板与核心思想：

  1. 递归函数：通常叫backtracking，参数包含当前路径path、当前选择位置startIndex等。
  2. 终止条件：当满足题目要求（如路径长度等于k）时，将当前路径加入结果集。
  3. 遍历选择：在当前层，遍历所有可能的选择。
  4. 做出选择：将选择加入路径。
  5. 递归进入下一层。
  6. 撤销选择（回溯）：将刚才加入路径的选择移除，恢复到之前的状态，以进行下一次尝试。

• 经典例题：77. 组合

  • 题意：从1到n中任选k个数的所有组合。
  • C++详解：

    class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking(int n, int k, int startIndex) { if (path.size() == k) { // 终止条件：路径长度等于k result.push_back(path); return; } // 遍历选择：从startIndex开始，到 n - (k - path.size()) + 1 进行剪枝 for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { path.push_back(i); // 做出选择 backtracking(n, k, i + 1); // 递归，下一层从i+1开始，避免重复 path.pop_back(); // 撤销选择，回溯 } } public: vector<vector<int>> combine(int n, int k) { result.clear(); path.clear(); backtracking(n, k, 1); return result; } };

  • 关键点：
    • startIndex：控制下一层递归的起始位置，保证组合内元素不重复且有序，避免出现[2,1]这样的重复组合。
    • 剪枝优化：循环条件i <= n - (k - path.size()) + 1。当前还需要k - path.size()个元素，从i开始最多还能选n - i + 1个元素。如果n - i + 1 < k - path.size()，即剩下的元素不够了，就没必要继续了。这是回溯算法性能优化的关键。

• 排列问题：46. 全排列

  • 与组合的区别：排列关注顺序，[1,2]和[2,1]是不同的。因此不需要startIndex，但需要used数组记录哪些元素已经被使用过。
  • C++实现：

    void backtrack(vector<int>& nums, vector<bool>& used) { if (path.size() == nums.size()) { result.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.pop_back(); used[i] = false; } }

6.2 动态规划：从记忆化搜索到状态转移

动态规划是解决具有重叠子问题和最优子结构问题的强大工具。其核心是定义状态和状态转移方程。

• 解题步骤：

  1. 确定dp数组及下标的含义。
  2. 确定递推公式（状态转移方程）。
  3. dp数组如何初始化。
  4. 确定遍历顺序。
  5. 举例推导dp数组（用于验证和调试）。

• 经典入门：70. 爬楼梯

  • 题意：每次可以爬1或2阶，到n阶有多少种方法。
  • 思路：
    • dp[i]：爬到第i阶楼梯的方法数。
    • 要想到达第i阶，可以从第i-1阶爬1步上来，也可以从第i-2阶爬2步上来。所以dp[i] = dp[i-1] + dp[i-2]。
    • 初始化：dp[1]=1,dp[2]=2（或dp[0]=1作为起点）。
  • C++实现（空间优化版）：

    int climbStairs(int n) { if (n <= 2) return n; int dp_i_2 = 1; // dp[i-2] int dp_i_1 = 2; // dp[i-1] int dp_i; for (int i = 3; i <= n; i++) { dp_i = dp_i_1 + dp_i_2; dp_i_2 = dp_i_1; dp_i_1 = dp_i; } return dp_i_1; // 循环结束时，dp_i_1就是dp[n] }

  • 关联：这就是斐波那契数列。很多简单DP问题都是斐波那契的变体。

• 背包问题基础：416. 分割等和子集（0-1背包）

  • 题意：判断数组是否能分成两个和相等的子集。
  • 转化为背包问题：数组总和为sum，目标就是找一些数，其和为target = sum/2。每个数只能选一次，这就是0-1背包。
  • DP定义：
    • dp[j]：容量为j的背包，能装的最大价值（这里价值=重量，即数字本身）。
    • 但本题是“能否装满”，所以可以定义dp[j]为：容量为j的背包，能否恰好装满（布尔值）。
  • 状态转移：对于当前数字nums[i]，如果j >= nums[i]，那么dp[j] = dp[j] || dp[j - nums[i]]。即，不选nums[i]（保持dp[j]）或选nums[i]（看j-nums[i]能否装满）。
  • C++实现：

    bool canPartition(vector<int>& nums) { int sum = accumulate(nums.begin(), nums.end(), 0); if (sum % 2 != 0) return false; // 和为奇数，不可能平分 int target = sum / 2; vector<bool> dp(target + 1, false); dp[0] = true; // 容量为0的背包，不装任何东西就是满的 for (int num : nums) { for (int j = target; j >= num; j--) { // 必须倒序遍历，保证每个物品只使用一次 dp[j] = dp[j] || dp[j - num]; } } return dp[target]; }

  • 关键心得：0-1背包的一维DP数组实现，内层循环必须倒序遍历容量。这是因为dp[j]依赖于上一轮（i-1）的dp[j-num]。正序遍历会覆盖掉上一轮的值，导致一个物品被重复使用（变成完全背包）。

6.3 贪心算法：局部最优与全局最优

贪心算法的核心是，每一步都做出当前看起来最优的选择，希望导致全局最优解。它不像动规有固定的公式，更考验对问题性质的洞察和证明。

• 简单贪心：455. 分发饼干
  • 题意：每个孩子有胃口值g[i]，每块饼干有尺寸s[j]，一块饼干最多满足一个胃口值小于等于它的孩子。求最多满足的孩子数。
  • 贪心策略：为了不浪费饼干，大饼干优先满足胃口大的孩子（或者小饼干优先满足胃口小的孩子）。这里采用“小饼干喂饱小胃口”。
  • 步骤：将g和s排序。用指针i遍历孩子，指针j遍历饼干。如果s[j] >= g[i]，则满足，两个指针都后移；否则只移动饼干指针j（尝试更大的饼干）。
  • C++实现：

    int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int i = 0, j = 0; while (i < g.size() && j < s.size()) { if (s[j] >= g[i]) { i++; // 满足一个孩子 } j++; // 无论是否满足，饼干都被尝试过了 } return i; // i就是被满足的孩子数量 }

  • 为什么贪心有效？可以反证：如果最优解中，有一块小饼干满足了一个大胃口的孩子，那么交换一下，用这块小饼干去满足一个更小的胃口（如果存在），不会使结果变差。所以排序后贪心匹配可以得到最优解。

贪心算法通常需要证明，但在面试中，能清晰阐述“为什么这样贪心”的思路往往比严格证明更重要。对于更复杂的贪心问题，如“区间调度”、“跳跃游戏”，需要多做练习来培养直觉。

7. 常见问题与排查技巧实录

在刷题和面试过程中，一些常见错误和调试技巧能帮你节省大量时间。

7.1 编译与语法错误

• vector下标越界：这是最常见的运行时错误。访问前务必检查索引i是否满足0 <= i < vec.size()。在循环中，注意边界条件。
• 空指针访问：对于指针或可能为nullptr的节点（如TreeNode*,ListNode*），在访问其成员（->val,->next）前必须判空。
• 使用未初始化的变量：局部变量不会自动初始化，使用前请赋值。特别是int,bool等基本类型。
• 函数返回值：确保所有控制路径都有返回值。编译器可能会报错“control reaches end of non-void function”。

7.2 逻辑与算法错误

• 无限递归：递归函数没有正确的终止条件，或终止条件永远达不到。检查递归基（base case）是否正确，递归参数是否向基 case 收敛。
• 死循环：while或for循环的终止条件写错，导致循环变量不更新或更新错误。在循环开始和结束时打印关键变量值有助于调试。
• 状态未回溯：在回溯算法中，忘记在递归返回后pop_back()或重置used数组，导致状态污染。
• DP数组初始化错误：dp[0]或边界条件的初始化至关重要。例如在背包问题中，dp[0]=0和dp[0]=1代表完全不同的含义。务必结合题意和递推公式推导初始化值。
• 整数溢出：当题目涉及大数运算（如阶乘、指数）或使用int进行累加时，注意结果可能超出int范围（约±21亿）。考虑使用long long。

7.3 调试与性能优化技巧

• 打印调试法：在关键位置（如循环开始/结束、递归入口/出口）打印变量状态。对于复杂数据结构（链表、树），可以编写简单的打印函数。
• 小数据测试：不要一上来就用复杂用例。先用题目给的示例，甚至自己构造更小的、边界的情况（空输入、单个元素）进行测试。
• 对比暴力法：如果你的优化算法结果不对，可以写一个简单但正确的暴力解法（如双重循环），在小数据上对比结果，定位错误。
• 复杂度分析：提交前，预估算法的时间和空间复杂度。如果超时（TLE），考虑是否存在更优算法（如用哈希表O(n)替代暴力O(n²)），或者递归/回溯中是否可以进行剪枝。
• 利用STL特性：unordered_map的[]运算符在key不存在时会插入默认值，而find方法不会。根据场景选择使用，避免意外插入。
• 容器选择：频繁在头部插入/删除用deque或list，随机访问用vector，查找用unordered_set/map（无序遍历）或set/map（有序遍历）。

7.4 面试实战技巧

• 先沟通，再动笔：拿到题目，先和面试官确认理解是否正确，阐述你的初步思路（暴力法、可能的优化方向），获得反馈后再开始写代码。
• 边写边讲：写代码时，解释你在做什么，为什么这么做。这展示了你的沟通能力和思维过程。
• 考虑边界：写完代码，主动提出测试一些边界情况（空、单元素、极大值、负数等）。
• 分析复杂度：代码完成后，主动分析时间复杂度和空间复杂度。
• 代码风格：使用有意义的变量名，适当添加注释，保持代码整洁。在C++中，注意const的正确使用，以及指针/引用的选择。

刷题是一个持续积累和反思的过程。这份笔记会随着我的学习和实践不断更新，补充更多经典的题目和更深入的解析。记住，目标不是刷完所有题，而是通过每一道题，掌握一类方法，构建起自己的算法知识网络。当你拿到一个新题，能快速将其归类到某个已知的模型或模式中时，你就真正入门了。