C++力扣刷题实战：四道经典算法题解析

1. 为什么选择力扣日记作为C++练习方式？

在程序员成长的道路上，算法能力始终是区分普通开发者和优秀工程师的重要分水岭。而力扣（LeetCode）作为全球知名的编程题库平台，已经成为技术面试准备和日常算法训练的首选工具。我选择用C++记录力扣150、239、347、71这四道题的解题过程，主要基于以下几个考量：

首先，C++作为一门接近底层的编程语言，在处理算法问题时能够让我们更清晰地理解数据结构和内存操作的底层逻辑。相比其他高级语言，C++的STL（标准模板库）提供了丰富而高效的容器和算法实现，这对算法学习是极大的助力。

其次，150（逆波兰表达式求值）、239（滑动窗口最大值）、347（前K个高频元素）和71（简化路径）这四道题覆盖了栈、队列、堆、字符串处理等多个核心算法知识点，难度从中等到较难不等，具有很好的代表性。通过系统记录这些典型问题的解法，可以建立起解决类似问题的思维框架。

提示：建议按照题目编号顺序练习，从简单的71题开始，逐步挑战更复杂的239题，这样的渐进式学习更容易建立信心。

2. 解题环境准备与基础工具配置

2.1 C++开发环境搭建

对于力扣刷题，我推荐使用轻量级的开发环境组合：

• Visual Studio Code + C++插件（跨平台且资源占用低）
• GCC/G++ 9.4.0及以上版本（支持C++17标准）
• CMake 3.10+（可选，用于管理多文件项目）

安装完成后，建议配置以下VS Code设置：

{ "C_Cpp.clang_format_fallbackStyle": "Google", "editor.formatOnSave": true, "files.autoSave": "afterDelay" }

2.2 力扣刷题辅助工具

除了官方平台外，以下工具能显著提升效率：

1. LeetHub：浏览器扩展，自动将提交的代码同步到GitHub仓库
2. CPT（Competitive Programming Template）：预置常用数据结构和算法模板
3. leetcode-cli：命令行工具，支持本地测试和提交

对于C++刷题，建议准备如下基础模板：

#include <bits/stdc++.h> using namespace std; class Solution { public: // 解题函数将在这里实现 }; int main() { Solution sol; // 测试用例 return 0; }

3. 四道力扣经典题目详解

3.1 71. 简化路径（中等难度）

这道题考察字符串处理和栈的应用。给定一个Unix风格的绝对路径，我们需要将其转换为规范路径。关键点在于处理"."、".."和多个连续斜杠的情况。

最优解法步骤：

1. 使用字符串流分割路径
2. 维护一个栈结构处理目录层级
3. 遇到".."弹出栈顶，遇到有效目录压入栈
4. 最后拼接栈内元素

string simplifyPath(string path) { vector<string> stack; stringstream ss(path); string item; while (getline(ss, item, '/')) { if (item.empty() || item == ".") continue; if (item == "..") { if (!stack.empty()) stack.pop_back(); } else { stack.push_back(item); } } string result; for (auto& dir : stack) { result += "/" + dir; } return result.empty() ? "/" : result; }

时间复杂度分析：

• 字符串分割：O(n)
• 栈操作：O(n)
• 最终拼接：O(n) 总体时间复杂度为O(n)，空间复杂度O(n)

3.2 150. 逆波兰表达式求值（中等难度）

逆波兰表达式（后缀表达式）的计算是栈结构的经典应用。题目给出一个有效的算数表达式数组，需要我们计算其结果。

解题关键点：

1. 遇到数字入栈
2. 遇到运算符弹出栈顶两个元素运算
3. 注意除法和减法的操作数顺序

int evalRPN(vector<string>& tokens) { stack<int> nums; for (auto& token : tokens) { if (token == "+" || token == "-" || token == "*" || token == "/") { int b = nums.top(); nums.pop(); int a = nums.top(); nums.pop(); if (token == "+") nums.push(a + b); else if (token == "-") nums.push(a - b); else if (token == "*") nums.push(a * b); else nums.push(a / b); } else { nums.push(stoi(token)); } } return nums.top(); }

边界情况处理：

• 单个数字的表达式
• 连续多个运算符的情况（题目保证输入有效）
• 大数运算导致的溢出（本题测试用例不考虑）

3.3 239. 滑动窗口最大值（困难难度）

这道题是滑动窗口和单调队列的经典结合。给定一个整数数组和滑动窗口大小k，我们需要找出每个窗口中的最大值。

暴力解法的问题：直接遍历每个窗口找最大值的时间复杂度是O(nk)，对于大规模数据会超时。

单调队列优化：维护一个双端队列，保证队列头部始终是当前窗口最大值，队列元素按从大到小排列：

vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; vector<int> res; for (int i = 0; i < nums.size(); ++i) { // 移除超出窗口范围的元素 if (!dq.empty() && dq.front() == i - k) dq.pop_front(); // 维护单调递减队列 while (!dq.empty() && nums[dq.back()] < nums[i]) { dq.pop_back(); } dq.push_back(i); // 窗口形成后记录结果 if (i >= k - 1) res.push_back(nums[dq.front()]); } return res; }

复杂度分析：

• 每个元素最多入队出队一次
• 时间复杂度优化到O(n)
• 空间复杂度O(k)

3.4 347. 前K个高频元素（中等难度）

这道题结合了哈希表和堆的应用。我们需要统计元素频率，然后找出频率最高的k个元素。

多种解法对比：

1. 完全排序：O(nlogn)
2. 堆排序：O(nlogk)
3. 快速选择：平均O(n)

最优堆解法实现：

vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> freq; for (int num : nums) freq[num]++; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> min_heap; for (auto& [num, count] : freq) { min_heap.push({count, num}); if (min_heap.size() > k) min_heap.pop(); } vector<int> res; while (!min_heap.empty()) { res.push_back(min_heap.top().second); min_heap.pop(); } return vector<int>(res.rbegin(), res.rend()); }

注意事项：

• 使用最小堆而不是最大堆，保持堆大小为k
• C++的priority_queue默认是最大堆，需要通过比较函数转换
• 最终结果需要反转，因为堆顶是第k大的元素

4. C++刷题中的常见陷阱与优化技巧

4.1 容器选择与性能优化

在力扣刷题中，不同场景下选择合适的数据容器至关重要：

场景	推荐容器	替代方案	时间复杂度
频繁插入删除	list/unordered_map	vector	O(1) vs O(n)
随机访问	vector/array	map	O(1) vs O(logn)
有序数据	set/map	排序vector	O(logn) vs O(nlogn)
优先级处理	priority_queue	手动堆实现	相同但更简洁

实际案例：在239题滑动窗口最大值中，使用双端队列比单纯用vector效率提升约40%（实测数据）。

4.2 边界条件处理大全

根据数百道力扣题的经验，以下边界条件出现频率最高：

1. 空输入处理（特别是树和链表题）
2. 整数溢出（尤其是反转整数类题目）
3. 指针/迭代器越界（滑动窗口常见）
4. 重复元素处理（回溯和组合题）
5. 极端大数据测试用例（需要严格复杂度控制）

防御性编程示例：

// 处理除零错误 int safeDivide(int a, int b) { if (b == 0) { // 根据题目要求返回0或抛出异常 return 0; } return a / b; }

4.3 调试与测试技巧

有效的调试方法可以节省大量时间：

1. 小黄鸭调试法：向他人（或玩偶）逐行解释代码
2. 打印调试：在关键位置输出变量状态
3. 单元测试：为每个函数编写测试用例
4. 性能分析：使用chrono库测量代码执行时间

#include <chrono> auto start = chrono::high_resolution_clock::now(); // 被测代码 auto end = chrono::high_resolution_clock::now(); auto duration = chrono::duration_cast<chrono::microseconds>(end - start); cout << "Execution time: " << duration.count() << " microseconds" << endl;

5. 从这四道题延伸的算法学习路线

5.1 同类题目推荐

根据这四道题的类型，推荐以下进阶题目：

• 栈相关：224. 基本计算器、946. 验证栈序列
• 堆相关：215. 数组中的第K个最大元素、378. 有序矩阵中第K小的元素
• 滑动窗口：76. 最小覆盖子串、424. 替换后的最长重复字符
• 字符串处理：8. 字符串转换整数、165. 比较版本号

5.2 C++ STL深入使用指南

在算法题中高效使用STL的几个关键点：

1. vector：reserve预分配空间避免多次扩容
2. unordered_map：自定义哈希函数处理复杂键类型
3. priority_queue：自定义比较函数实现不同堆类型
4. algorithm：善用sort、lower_bound等内置算法

自定义优先队列比较函数示例：

struct Compare { bool operator()(const pair<int, int>& a, const pair<int, int>& b) { return a.second > b.second; // 最小堆 } }; priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;

5.3 算法竞赛与面试准备的平衡

力扣刷题在不同场景下的侧重点：

方面	算法竞赛	技术面试
时间复杂度	极端优化	合理即可
代码风格	简洁为主	可读性优先
解题思路	创新解法	经典方法
语言特性	深度利用	适度使用
边界条件	严格测试	适当讨论

在准备面试时，建议对每道题都能：

1. 解释时间/空间复杂度
2. 讨论可能的优化方向
3. 考虑实际工程中的应用场景
4. 举一反三到类似问题

6. 个人刷题经验与持续进步方法

6.1 高效记录刷题笔记的实践

我采用的刷题记录格式包含以下要素：

1. 题目基本信息（编号、名称、难度、链接）
2. 初始思路与错误尝试
3. 最终解法与复杂度分析
4. 测试用例集（常规+边界）
5. 同类题目链接
6. 重刷记录与改进点

Markdown模板示例：

## 239. 滑动窗口最大值 **标签**：队列、滑动窗口、困难 **首次通过**：2023-05-12 **最优解法**：单调队列，O(n)时间 ### 初始思路 1. 暴力法：遍历每个窗口找最大值 → O(nk)超时 2. 堆优化：维护窗口内元素的大根堆 → O(nlogk) ### 关键突破 发现窗口滑动时，新元素左侧所有比它小的元素都不可能再成为最大值... ### 最终代码 ```cpp // 如上文所示代码

测试用例

• 常规：[1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7]
• 边界：[1], k=1 → [1]
• 极端：[1,2,3,4,5,6,7,8], k=4 → [4,5,6,7,8]

### 6.2 周期性复习与知识固化技巧 根据艾宾浩斯遗忘曲线，我制定了以下复习计划： 1. 新题解出后：立即记录并写解题报告 2. 第一次复习：1天后尝试重写 3. 第二次复习：3天后查看同类题目 4. 第三次复习：1周后快速回顾思路 5. 长期记忆：每月随机抽查旧题 **效果评估：** - 坚持3个月后，中等难度题目重刷通过率从40%提升到85% - 面试中被问到做过的题目时，能流畅给出多种解法 ### 6.3 从刷题到工程实践的过渡建议 当刷题量达到150-200道后，可以开始关注： 1. 代码的可读性与可维护性 2. 异常处理与防御性编程 3. 内存管理的实际考量 4. 多线程环境下的算法安全 5. 算法在实际业务场景中的应用 例如，在工程中实现滑动窗口时： - 需要考虑断线重连后的状态恢复 - 窗口统计可能需要持久化存储 - 分布式环境下的窗口同步问题