1. C++刷题笔记的价值与结构设计

刷题笔记对于程序员来说就像厨师的私房菜谱，记录着解题过程中的关键思路和技巧。我整理C++刷题笔记已有五年时间，从最初零散的代码片段到现在系统化的知识库，这套方法帮助我在算法面试中保持了90%以上的通过率。

好的刷题笔记应该包含三个核心要素：问题归类、解法分析和代码模板。不同于简单的AC代码收藏夹，有价值的笔记会记录下解题时的思维过程，包括错误的尝试和优化的路径。比如在解决动态规划问题时，我会特意保留最初设计的低效状态转移方程，旁边标注优化思路，这种对比学习效果远超单纯背诵最优解。

2. 数据结构的高效运用技巧

2.1 STL容器的实战选择

vector和deque的选择常常让新手纠结。在处理滑动窗口问题时，deque的前后O(1)操作特性使其成为不二之选。我曾在一个股票买卖问题中测试过，使用deque比vector快3倍以上。关键代码片段：

deque<int> q; for(int i=0; i<n; ++i){ while(!q.empty() && prices[q.back()]>=prices[i]) q.pop_back(); q.push_back(i); // 维护窗口大小 if(i-q.front()+1 > k) q.pop_front(); }

注意：deque的迭代器失效规则比vector复杂，在中间位置插入删除时要特别小心。

2.2 自定义哈希函数的实现

当需要把自定义结构体作为unordered_map的key时，标准库的哈希函数往往不够用。比如处理图论问题时，用pair表示边就很常见：

struct pair_hash{ template<class T1, class T2> size_t operator()(const pair<T1,T2>& p) const{ auto h1 = hash<T1>{}(p.first); auto h2 = hash<T2>{}(p.second); return h1 ^ (h2 << 1); } }; unordered_map<pair<int,int>, int, pair_hash> edge_map;

这个实现有个潜在问题：当h1和h2相近时，异或操作会导致信息丢失。更稳妥的做法是用质数相乘：

return h1 * 31 + h2; // 31是经验质数

3. 算法模板的深度优化

3.1 二分查找的边界处理

二分查找看似简单，但边界条件极易出错。我总结出"循环不变量"法则：明确维护的区间性质。比如在旋转数组查找中：

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; }

关键点：mid计算方式可防止(l+r)溢出；等号放在nums[l]<=nums[mid]这一边处理边界情况。

3.2 回溯算法的剪枝艺术

N皇后问题是最经典的回溯案例，但朴素解法在N=12时就可能超时。通过位运算优化和对称性剪枝，我能将N=16的运行时间从30秒降到2秒：

void backtrack(int row, int ld, int rd, int n, int& count){ if(row == (1<<n)-1){ // 所有列已放置 count++; return; } int pos = ((1<<n)-1) & ~(row|ld|rd); // 可用位置 while(pos){ int p = pos & -pos; // 取最低位的1 pos -= p; // 标记已尝试 backtrack(row|p, (ld|p)<<1, (rd|p)>>1, n, count); } }

这个实现有三大优化点：

1. 用位掩码替代二维数组记录攻击范围
2. 通过lowbit运算快速枚举可选位置
3. 利用位运算的并行性加速冲突检测

4. 调试与性能调优实战

4.1 内存错误的诊断技巧

段错误(Segmentation Fault)是C++刷题时的常见噩梦。我常用的诊断流程：

1. 使用AddressSanitizer编译：g++ -fsanitize=address -g
2. 检查vector/string的越界访问
3. 验证指针是否在解引用前判空
4. 递归算法检查栈溢出

最近遇到的一个典型案例：

vector<int> vec(10); int& val = vec[10]; // 越界 cout << val; // 可能不立即崩溃

经验：在Online Judge环境中，有时越界访问不会立即导致RE，而是表现为WA。这种隐蔽的错误最耗时。

4.2 时间复杂度分析实战

快速判断算法是否超时有个经验法则：在1秒时间限制下：

• 1e6操作：O(n)或O(nlogn)安全
• 1e5操作：O(nlogn)安全
• 1e4操作：O(n^2)可能通过

我曾用这个规则在竞赛中快速优化了一个O(n^2)的LIS解法：

// 原始DP O(n^2) for(int i=1; i<n; ++i) for(int j=0; j<i; ++j) if(nums[j]<nums[i]) dp[i]=max(dp[i],dp[j]+1); // 优化为O(nlogn)的贪心+二分 vector<int> tail; for(int num : nums){ auto it = lower_bound(tail.begin(), tail.end(), num); if(it == tail.end()) tail.push_back(num); else *it = num; } return tail.size();

5. 代码风格与可维护性

5.1 防御性编程习惯

刷题代码虽然短小，但良好的编码习惯能减少80%的调试时间。我的必备防御措施：

1. 数组/容器访问前检查索引
2. 指针解引用前验证非空
3. 数学运算警惕除零和溢出
4. 递归函数设置深度限制

例如处理二叉树时：

int maxDepth(TreeNode* root) { if(!root) return 0; // 防御空指针 queue<TreeNode*> q; q.push(root); int depth = 0; while(!q.empty()){ int size = q.size(); // 提前获取，避免循环中变化 while(size--){ auto node = q.front(); q.pop(); if(node->left) q.push(node->left); // 判空 if(node->right) q.push(node->right); } depth++; } return depth; }

5.2 模块化代码模板

将常用算法封装成即插即用的代码块能大幅提高解题速度。我的模板库包含：

1. 并查集(Union-Find)带路径压缩
2. 快速幂模运算
3. 前缀和与差分数组
4. Dijkstra最短路径实现

以Dijkstra算法为例：

vector<int> dijkstra(vector<vector<pair<int,int>>>& graph, int start){ int n = graph.size(); vector<int> dist(n, INT_MAX); dist[start] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; pq.emplace(0, start); while(!pq.empty()){ auto [d, u] = pq.top(); pq.pop(); if(d > dist[u]) continue; // 旧数据跳过 for(auto [v, w] : graph[u]){ if(dist[v] > dist[u] + w){ dist[v] = dist[u] + w; pq.emplace(dist[v], v); } } } return dist; }

这个实现有三个优化点：

1. 使用小顶堆替代普通队列
2. 延迟删除旧数据而非实时更新堆
3. 使用pair而非自定义结构体，减少代码量

6. 刷题进阶路线建议

从我的经验看，有效的刷题路径应该分四个阶段：

1. 基础语法阶段：掌握STL容器和基本算法
2. 专题突破阶段：按算法类型集中训练
3. 综合应用阶段：解决LeetCode周赛级别问题
4. 竞赛强化阶段：挑战Codeforces D题以上难度

每个阶段的典型标志：

• 阶段1：能独立实现快速排序和归并排序
• 阶段2：能分辨动态规划的背包问题与区间DP差异
• 阶段3：能在30分钟内完成中等难度题目
• 阶段4：能灵活运用线段树等高级数据结构

我个人的转折点是系统性地整理了200道题目的同类解法，发现很多问题本质上是相同模型的变种。比如滑动窗口问题，核心都是维护一个满足特定性质的窗口：

int left = 0, right = 0; while(right < n){ // 扩展右边界 window.add(s[right]); right++; // 收缩左边界直到满足条件 while(window.need_shrink()){ window.remove(s[left]); left++; } // 处理当前窗口 update_result(); }

掌握这个范式后，从最小覆盖子串到最长无重复子串都能迎刃而解。这种模式识别的能力，才是刷题笔记应该培养的核心竞争力。