1. 项目概述力扣刷题的C实践记录最近在整理自己的力扣刷题笔记时发现C解法往往能提供独特的视角和高效的实现。这篇日记将分享我在解决150逆波兰表达式求值、239滑动窗口最大值、347前K个高频元素和71简化路径这四道题目时的思考过程和代码实现。这些题目覆盖了栈、队列、堆等数据结构的典型应用场景对准备技术面试很有帮助。2. 题目解析与实现思路2.1 150. 逆波兰表达式求值逆波兰表达式后缀表达式的计算是栈结构的经典应用。遇到数字就压栈遇到运算符就弹出栈顶两个元素进行计算再将结果压回栈中。int evalRPN(vectorstring tokens) { stackint st; for (const auto token : tokens) { if (token || token - || token * || token /) { int b st.top(); st.pop(); int a st.top(); st.pop(); if (token ) st.push(a b); else if (token -) st.push(a - b); else if (token *) st.push(a * b); else st.push(a / b); } else { st.push(stoi(token)); } } return st.top(); }注意除法的处理要特别注意题目保证除法结果会向零截断所以直接使用整数除法即可。2.2 239. 滑动窗口最大值这道题要求我们在O(n)时间复杂度内解决普通的暴力解法无法满足要求。这里使用双端队列维护一个单调递减的队列vectorint maxSlidingWindow(vectorint nums, int k) { dequeint dq; vectorint 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; }2.3 347. 前K个高频元素这道题考察堆的使用。我们可以先用哈希表统计频率然后用最小堆来维护前K个高频元素vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int freq; for (int num : nums) freq[num]; auto cmp [freq](int a, int b) { return freq[a] freq[b]; }; priority_queueint, vectorint, decltype(cmp) pq(cmp); for (auto p : freq) { pq.push(p.first); if (pq.size() k) pq.pop(); } vectorint res; while (!pq.empty()) { res.push_back(pq.top()); pq.pop(); } return res; }2.4 71. 简化路径这道题需要处理Unix风格的路径字符串使用栈来处理路径中的.和..string simplifyPath(string path) { vectorstring st; stringstream ss(path); string dir; while (getline(ss, dir, /)) { if (dir.empty() || dir .) continue; if (dir ..) { if (!st.empty()) st.pop_back(); } else { st.push_back(dir); } } string res; for (const auto s : st) { res / s; } return res.empty() ? / : res; }3. 解题技巧与优化思路3.1 数据结构的选择与比较在解决这些问题时数据结构的选择至关重要栈适合处理对称性、递归性问题如150题队列/双端队列适合处理滑动窗口、BFS相关问题如239题堆适合处理Top K问题如347题哈希表适合快速查找和频率统计3.2 C标准库的高效使用C标准库提供了丰富的数据结构实现合理使用可以大幅提升编码效率std::stack和std::queue是适配器容器底层默认使用dequestd::priority_queue默认是大顶堆可以通过自定义比较函数实现小顶堆std::unordered_map比std::map有更好的平均时间复杂度O(1) vs O(log n)3.3 边界条件处理在刷题过程中边界条件的处理往往决定成败空输入的处理极端值如最大/最小值的处理特殊字符或格式的处理循环终止条件的判断4. 常见问题与调试技巧4.1 调试技巧打印中间结果在关键步骤后打印变量值使用断言验证不变量和前提条件单元测试为每个函数编写测试用例4.2 性能优化减少不必要的拷贝使用引用传递参数预分配内存对于已知大小的容器提前reserve选择合适的数据结构根据操作特点选择最优结构4.3 编码风格建议变量命名要有意义适当添加注释解释复杂逻辑保持函数短小精悍单一职责错误处理要明确5. 力扣刷题的系统性方法5.1 题目分类训练建议按照题目类型进行集中训练比如数组与字符串链表树与图动态规划贪心算法5.2 错题本与复盘建立自己的错题本记录初次解题的思路遇到的坑和错误最优解的分析同类题目的变形5.3 时间管理与模拟面试在准备面试时限时练习如30分钟一题模拟白板编程练习口头解释思路6. C刷题的特殊考量6.1 语言特性利用移动语义减少不必要的拷贝智能指针管理动态内存Lambda表达式简化回调实现6.2 标准库算法熟练使用algorithm中的常用函数sort/stable_sortlower_bound/upper_boundnext_permutationaccumulate6.3 内存与性能注意容器扩容的成本避免不必要的动态内存分配考虑缓存友好性刷题不仅是解决问题的过程更是培养计算思维和编程习惯的好方法。通过系统地记录和复盘可以显著提升算法能力和编码水平。 
长河君 · 2026/10/28 14:29:58 · 阅读 1.2k 力扣刷题C++实践：栈、队列与堆的应用解析
1. 项目概述力扣刷题的C实践记录最近在整理自己的力扣刷题笔记时发现C解法往往能提供独特的视角和高效的实现。这篇日记将分享我在解决150逆波兰表达式求值、239滑动窗口最大值、347前K个高频元素和71简化路径这四道题目时的思考过程和代码实现。这些题目覆盖了栈、队列、堆等数据结构的典型应用场景对准备技术面试很有帮助。2. 题目解析与实现思路2.1 150. 逆波兰表达式求值逆波兰表达式后缀表达式的计算是栈结构的经典应用。遇到数字就压栈遇到运算符就弹出栈顶两个元素进行计算再将结果压回栈中。int evalRPN(vectorstring tokens) { stackint st; for (const auto token : tokens) { if (token || token - || token * || token /) { int b st.top(); st.pop(); int a st.top(); st.pop(); if (token ) st.push(a b); else if (token -) st.push(a - b); else if (token *) st.push(a * b); else st.push(a / b); } else { st.push(stoi(token)); } } return st.top(); }注意除法的处理要特别注意题目保证除法结果会向零截断所以直接使用整数除法即可。2.2 239. 滑动窗口最大值这道题要求我们在O(n)时间复杂度内解决普通的暴力解法无法满足要求。这里使用双端队列维护一个单调递减的队列vectorint maxSlidingWindow(vectorint nums, int k) { dequeint dq; vectorint 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; }2.3 347. 前K个高频元素这道题考察堆的使用。我们可以先用哈希表统计频率然后用最小堆来维护前K个高频元素vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int freq; for (int num : nums) freq[num]; auto cmp [freq](int a, int b) { return freq[a] freq[b]; }; priority_queueint, vectorint, decltype(cmp) pq(cmp); for (auto p : freq) { pq.push(p.first); if (pq.size() k) pq.pop(); } vectorint res; while (!pq.empty()) { res.push_back(pq.top()); pq.pop(); } return res; }2.4 71. 简化路径这道题需要处理Unix风格的路径字符串使用栈来处理路径中的.和..string simplifyPath(string path) { vectorstring st; stringstream ss(path); string dir; while (getline(ss, dir, /)) { if (dir.empty() || dir .) continue; if (dir ..) { if (!st.empty()) st.pop_back(); } else { st.push_back(dir); } } string res; for (const auto s : st) { res / s; } return res.empty() ? / : res; }3. 解题技巧与优化思路3.1 数据结构的选择与比较在解决这些问题时数据结构的选择至关重要栈适合处理对称性、递归性问题如150题队列/双端队列适合处理滑动窗口、BFS相关问题如239题堆适合处理Top K问题如347题哈希表适合快速查找和频率统计3.2 C标准库的高效使用C标准库提供了丰富的数据结构实现合理使用可以大幅提升编码效率std::stack和std::queue是适配器容器底层默认使用dequestd::priority_queue默认是大顶堆可以通过自定义比较函数实现小顶堆std::unordered_map比std::map有更好的平均时间复杂度O(1) vs O(log n)3.3 边界条件处理在刷题过程中边界条件的处理往往决定成败空输入的处理极端值如最大/最小值的处理特殊字符或格式的处理循环终止条件的判断4. 常见问题与调试技巧4.1 调试技巧打印中间结果在关键步骤后打印变量值使用断言验证不变量和前提条件单元测试为每个函数编写测试用例4.2 性能优化减少不必要的拷贝使用引用传递参数预分配内存对于已知大小的容器提前reserve选择合适的数据结构根据操作特点选择最优结构4.3 编码风格建议变量命名要有意义适当添加注释解释复杂逻辑保持函数短小精悍单一职责错误处理要明确5. 力扣刷题的系统性方法5.1 题目分类训练建议按照题目类型进行集中训练比如数组与字符串链表树与图动态规划贪心算法5.2 错题本与复盘建立自己的错题本记录初次解题的思路遇到的坑和错误最优解的分析同类题目的变形5.3 时间管理与模拟面试在准备面试时限时练习如30分钟一题模拟白板编程练习口头解释思路6. C刷题的特殊考量6.1 语言特性利用移动语义减少不必要的拷贝智能指针管理动态内存Lambda表达式简化回调实现6.2 标准库算法熟练使用algorithm中的常用函数sort/stable_sortlower_bound/upper_boundnext_permutationaccumulate6.3 内存与性能注意容器扩容的成本避免不必要的动态内存分配考虑缓存友好性刷题不仅是解决问题的过程更是培养计算思维和编程习惯的好方法。通过系统地记录和复盘可以显著提升算法能力和编码水平。