C++刷题笔记：数据结构与算法实战技巧

1. C刷题笔记的价值与结构设计刷题笔记对于程序员来说就像厨师的私房菜谱记录着解题过程中的关键思路和技巧。我整理C刷题笔记已有五年时间从最初零散的代码片段到现在系统化的知识库这套方法帮助我在算法面试中保持了90%以上的通过率。好的刷题笔记应该包含三个核心要素问题归类、解法分析和代码模板。不同于简单的AC代码收藏夹有价值的笔记会记录下解题时的思维过程包括错误的尝试和优化的路径。比如在解决动态规划问题时我会特意保留最初设计的低效状态转移方程旁边标注优化思路这种对比学习效果远超单纯背诵最优解。2. 数据结构的高效运用技巧2.1 STL容器的实战选择vector和deque的选择常常让新手纠结。在处理滑动窗口问题时deque的前后O(1)操作特性使其成为不二之选。我曾在一个股票买卖问题中测试过使用deque比vector快3倍以上。关键代码片段dequeint q; for(int i0; in; 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{ templateclass T1, class T2 size_t operator()(const pairT1,T2 p) const{ auto h1 hashT1{}(p.first); auto h2 hashT2{}(p.second); return h1 ^ (h2 1); } }; unordered_mappairint,int, int, pair_hash edge_map;这个实现有个潜在问题当h1和h2相近时异或操作会导致信息丢失。更稳妥的做法是用质数相乘return h1 * 31 h2; // 31是经验质数3. 算法模板的深度优化3.1 二分查找的边界处理二分查找看似简单但边界条件极易出错。我总结出循环不变量法则明确维护的区间性质。比如在旋转数组查找中int search(vectorint nums, int target) { int l0, rnums.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 targetnums[mid]) rmid-1; else lmid1; }else{ // 右有序 if(nums[mid]target targetnums[r]) lmid1; else rmid-1; } } return -1; }关键点mid计算方式可防止(lr)溢出等号放在nums[l]nums[mid]这一边处理边界情况。3.2 回溯算法的剪枝艺术N皇后问题是最经典的回溯案例但朴素解法在N12时就可能超时。通过位运算优化和对称性剪枝我能将N16的运行时间从30秒降到2秒void backtrack(int row, int ld, int rd, int n, int count){ if(row (1n)-1){ // 所有列已放置 count; return; } int pos ((1n)-1) ~(row|ld|rd); // 可用位置 while(pos){ int p pos -pos; // 取最低位的1 pos - p; // 标记已尝试 backtrack(row|p, (ld|p)1, (rd|p)1, n, count); } }这个实现有三大优化点用位掩码替代二维数组记录攻击范围通过lowbit运算快速枚举可选位置利用位运算的并行性加速冲突检测4. 调试与性能调优实战4.1 内存错误的诊断技巧段错误(Segmentation Fault)是C刷题时的常见噩梦。我常用的诊断流程使用AddressSanitizer编译g -fsanitizeaddress -g检查vector/string的越界访问验证指针是否在解引用前判空递归算法检查栈溢出最近遇到的一个典型案例vectorint 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 i1; in; i) for(int j0; ji; j) if(nums[j]nums[i]) dp[i]max(dp[i],dp[j]1); // 优化为O(nlogn)的贪心二分 vectorint 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%的调试时间。我的必备防御措施数组/容器访问前检查索引指针解引用前验证非空数学运算警惕除零和溢出递归函数设置深度限制例如处理二叉树时int maxDepth(TreeNode* root) { if(!root) return 0; // 防御空指针 queueTreeNode* 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 模块化代码模板将常用算法封装成即插即用的代码块能大幅提高解题速度。我的模板库包含并查集(Union-Find)带路径压缩快速幂模运算前缀和与差分数组Dijkstra最短路径实现以Dijkstra算法为例vectorint dijkstra(vectorvectorpairint,int graph, int start){ int n graph.size(); vectorint dist(n, INT_MAX); dist[start] 0; priority_queuepairint,int, vectorpairint,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; }这个实现有三个优化点使用小顶堆替代普通队列延迟删除旧数据而非实时更新堆使用pair而非自定义结构体减少代码量6. 刷题进阶路线建议从我的经验看有效的刷题路径应该分四个阶段基础语法阶段掌握STL容器和基本算法专题突破阶段按算法类型集中训练综合应用阶段解决LeetCode周赛级别问题竞赛强化阶段挑战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(); }掌握这个范式后从最小覆盖子串到最长无重复子串都能迎刃而解。这种模式识别的能力才是刷题笔记应该培养的核心竞争力。