1. 项目缘起：为什么是华为机试与C++的108题？

如果你正在准备技术面试，尤其是国内一些大厂的研发岗位，那么“华为机试”这四个字对你来说一定不陌生。它不是一个官方发布的固定题库，而是求职者社群中口口相传、经过无数人实战检验后，总结出的一个高频算法与编程题的集合。这个集合之所以被冠以“华为”之名，是因为其中的题目风格、难度和考察点，与华为技术面试中的编程环节高度重合。而“108题”这个数字，更像是一个象征，代表着覆盖核心考点的题量规模。

我之所以花三个月时间，用C++把这108题从头到尾“爆肝”了一遍，并非一时兴起。几年前，我自己在准备面试时，就深受这类题库的恩惠。但当时能找到的解析，要么是Java版，要么是Python版，C++的完整、系统且适合新手的解析相对零散。很多解析只给代码，不讲背后的数据结构选择逻辑，也不谈C++标准库（STL）的巧妙运用，更别提那些编译报错、边界处理的坑了。对于C++新手，或者从其他语言转过来的朋友，看懂了算法思路，却卡在 vector 的初始化、 unordered_map 的遍历，或者内存管理上，非常打击信心。

所以，这个系列的目标非常明确： 为使用C++备战机试的初学者和求职者，提供一套“保姆级”的解题指南 。它不仅仅是答案的罗列，更是我作为过来人，对每道题“为什么用这个数据结构”、“STL组件在这里怎么用最优雅”、“常见的坑点在哪里”的一次系统性梳理。无论你是科班学生巩固基础，还是跨专业求职急需刷题，希望这份耗时三个月整理的“心血”，能成为你书架上（或浏览器收藏夹里）常备的参考。

2. 攻坚利器：C++与STL在算法解题中的核心优势

在开始具体题目之前，我们必须统一思想：为什么选择C++来刷算法题？特别是对于“华为机试”这类偏向底层、注重效率和内存控制的场景，C++搭配STL（标准模板库）的组合，几乎是最锋利的“手术刀”。

2.1 效率与控制的平衡

C++以其接近硬件的特性，提供了无与伦比的性能控制能力。在算法题中，这意味着你可以精确地管理内存（虽然现代C++提倡RAII，减少手动 new/delete ），优化循环，甚至利用编译期计算。但纯粹的手写一切（比如自己实现链表、哈希表）在笔试的有限时间内是灾难。这时，STL的价值就凸显出来了。它提供了一套经过千锤百炼、高度优化的通用容器和算法组件。你无需重复造轮子，却能享受到接近手写代码的效率。例如， std::sort 的底层通常是快速排序、堆排序和插入排序的混合（IntroSort），其效率远超绝大多数面试者现场手写的排序。

2.2 STL：你的算法武器库

STL是C++刷题的核心竞争力。理解并熟练运用以下几个组件，解题效率能提升数倍：

• 序列容器 ：

  • vector ：动态数组，随机访问O(1)，尾部插入删除平均O(1)。 这是使用频率最高的容器，没有之一。 绝大多数需要数组的场景，优先考虑 vector 。
  • string ：本质是 vector<char> ，但提供了丰富的字符串操作接口（ find , substr , append 等），处理字符串题目必不可少。
  • deque ：双端队列，头尾插入删除O(1)。适合滑动窗口最大值等问题。
  • list / forward_list ：链表。在需要频繁中间插入删除且不需要随机访问时使用，但机试中较少直接使用。

• 关联容器 ：

  • set / multiset ：基于红黑树的集合，元素自动排序，查找、插入、删除O(log n)。用于需要有序且去重（或不去重）的场景。
  • map / multimap ：基于红黑树的键值对，同样自动按键排序。 map[key] 访问若 key 不存在会自动插入，有时需用 find 方法先判断。
  • unordered_set / unordered_map ：基于哈希表的集合和映射，查找、插入、删除平均O(1)，最坏O(n)。 在不需要元素顺序，只需要快速查找、去重或计数的场景下，这是首选。 例如“两数之和”、“第一个只出现一次的字符”等题目。

• 容器适配器 ：

  • stack ：后进先出（LIFO），通常用 deque 或 list 作为底层容器。用于括号匹配、表达式求值、DFS非递归。
  • queue ：先进先出（FIFO），用于BFS。
  • priority_queue ：优先队列（堆），默认是大顶堆。用于Top K、求中位数、Dijkstra算法等。 这是实现堆数据结构最便捷的方式。

• 算法头文件 <algorithm> ：

  • sort , stable_sort ：排序。
  • lower_bound / upper_bound ：在有序序列中二分查找，返回迭代器。
  • next_permutation / prev_permutation ：生成全排列。
  • max_element , min_element , accumulate ：找最大最小、求和。
  • unique ：与 erase 配合，去除有序序列中的连续重复项。

2.3 实战中的STL选择策略

一个简单的决策流：需要快速查找键值对？用 unordered_map 。需要有序集合？用 set 。需要动态数组？用 vector 。需要后进先出？用 stack 。需要前K个最大/最小？用 priority_queue 。在解题时，先问自己核心操作是什么，再根据时间复杂度选择最合适的STL工具，这是从“暴力求解”到“优雅AC”的关键一步。

3. 核心算法思想精讲与108题中的典型应用

108题虽然题量不小，但剥开外壳，其核心算法思想是有限的。掌握以下思想，并学会在具体题目中识别和应用它们，比盲目刷完所有题目更重要。

3.1 双指针与滑动窗口

这是处理数组/字符串子区间、子序列问题的最常用技巧。

• 对撞指针 ：常用于有序数组，一左一右向中间移动。典型问题：两数之和（有序数组版）、三数之和、盛最多水的容器。

  // 两数之和 II - 输入有序数组 示例
  vector<int> twoSum(vector<int>& numbers, int target) {
      int left = 0, right = numbers.size() - 1;
      while (left < right) {
          int sum = numbers[left] + numbers[right];
          if (sum == target) return {left + 1, right + 1}; // 题目要求索引从1开始
          else if (sum < target) ++left;
          else --right;
      }
      return {};
  }
  

• 快慢指针 ：常用于链表判环、找中点，或数组去重。快指针每次走两步，慢指针走一步。
• 滑动窗口 ：维护一个区间，通过移动左右边界来寻找符合条件的子串/子数组。常用于“最小覆盖子串”、“长度最小的子数组”、“不含重复字符的最长子串”。

  // 无重复字符的最长子串 示例框架
  int lengthOfLongestSubstring(string s) {
      unordered_map<char, int> window; // 记录窗口内字符出现次数
      int left = 0, right = 0;
      int maxLen = 0;
      while (right < s.size()) {
          char c = s[right];
          right++;
          window[c]++; // 扩大窗口
          // 当窗口内出现重复字符时，收缩左侧
          while (window[c] > 1) {
              char d = s[left];
              left++;
              window[d]--;
          }
          // 更新答案
          maxLen = max(maxLen, right - left);
      }
      return maxLen;
  }
  

3.2 深度优先搜索（DFS）与广度优先搜索（BFS）

这是遍历树和图的基本方法，也用于解决回溯、路径规划等问题。

• DFS ：通常用递归或栈实现，一条路走到黑，再回溯。用于排列、组合、子集、棋盘类（如N皇后）、图的连通分量等问题。

  // 二叉树的中序遍历 (递归DFS)
  void inorder(TreeNode* root, vector<int>& res) {
      if (!root) return;
      inorder(root->left, res); // 左
      res.push_back(root->val); // 根
      inorder(root->right, res); // 右
  }
  

• BFS ：通常用队列实现，一层一层向外扩展。用于求最短路径（在无权图中）、层次遍历二叉树、扩散类问题（如岛屿数量）。

  // 二叉树的层序遍历 (BFS)
  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;
  }
  

3.3 动态规划（Dynamic Programming）

动态规划是解决最优化问题的神器，也是机试中的难点和重点。其核心思想是 将复杂问题分解为重叠子问题，并存储子问题的解以避免重复计算 。

• 解题步骤 ：

  1. 定义状态 ： dp[i] 或 dp[i][j] 代表什么？这是最关键也最难的一步。
  2. 状态转移方程 ：如何从已知状态推导出 dp[i][j] ？这是DP的核心逻辑。
  3. 初始化 ：最基础、不可再分的子问题的解是什么？
  4. 确定遍历顺序 ：确保在计算当前状态时，它所依赖的子状态已经被计算过。
  5. 输出结果 ：最终答案对应哪个状态？

• 经典模型在108题中的体现 ：

  • 背包问题 ： dp[i][j] 表示前i个物品在容量j下的最大价值。01背包和完全背包的状态转移方程是基础。
  • 路径问题 ： dp[i][j] 表示到达 (i, j) 的路径数或最小代价。通常 dp[i][j] = dp[i-1][j] + dp[i][j-1] 或加上代价。
  • 子序列问题 ：最长递增子序列（LIS）、最长公共子序列（LCS）、编辑距离。 dp[i][j] 常表示以 i 和 j 结尾的子序列的性质。
  • 打家劫舍/股票问题 ：状态常设计为 dp[i][0] 和 dp[i][1] ，分别表示第i天“不持有”和“持有”某种状态时的最大收益。

注意 ：动态规划题目往往有多种解法，记忆化搜索（递归+备忘录）是自顶向下的DP，而递推是自底向上。对于新手，先从递推开始理解状态转移的链条更直观。在108题中，我会对每道DP题都详细拆解状态定义和转移方程的思考过程。

3.4 贪心算法

贪心算法在每一步都做出当前看来最优的选择，希望导致全局最优。它比DP更高效，但 需要证明贪心策略的正确性 ，否则可能得到错误答案。

• 典型应用 ：区间调度（最多不相交区间）、分糖果、找零钱（特定面额）、跳跃游戏。
• 示例：跳跃游戏 II 。贪心策略是：在当前位置可跳范围内，选择那个“ 位置 + 可跳距离 ”最远的点作为下一跳的起跳点之一，从而保证跳跃次数最少。

3.5 二分查找

二分查找不仅用于有序数组找目标值，更是一种“在有序解空间中寻找边界”的思想。

• 变体 ：寻找第一个等于目标值的位置、最后一个等于目标值的位置、第一个大于等于目标值的位置等。这些变体关键在于循环条件（ left <= right 还是 < ）和边界更新（ mid +/- 1 ）的细微差别。
• 应用 ：除了搜索，还用于“最大值最小化”或“最小值最大化”问题（如分割数组的最大值、在D天内送达包裹的能力）。这类问题通常难以直接求解，但给定一个候选答案 X ，我们可以容易地判断是否可行。于是，解空间（答案的可能范围）是单调有序的，就可以用二分查找来快速定位最优解。

4. 从新手到熟练：三个月“爆肝”计划与实操心法

知道了“武器”（C++/STL）和“兵法”（算法思想），如何通过108题这个“战场”来练就真功夫？下面是我亲身实践并验证有效的三个月学习计划与心法。

4.1 阶段规划：循序渐进，巩固阵地

• 第一个月：基础夯实期（约30题）

  • 目标 ：熟悉C++基本语法、输入输出、STL容器的基础操作。攻克数组、字符串、链表、栈、队列、哈希表相关的基础题目。
  • 每日任务 ：精做1-2题。重点不在数量，而在彻底搞懂。每道题至少用两种方法实现（如暴力法和优化法）。详细记录解题思路，画出流程图或状态图。
  • 核心输出 ：建立自己的代码模板库，例如快速输入输出、二叉树的建立与遍历、常见排序等。

• 第二个月：算法深化期（约50题）

  • 目标 ：重点攻坚双指针、滑动窗口、DFS/BFS、回溯、动态规划、贪心等核心算法。开始接触中等难度题目。
  • 每日任务 ：保持每天2-3题的节奏。对于DP和回溯题，必须手动推导状态转移方程或画出递归树。尝试对同一题型进行归纳（如背包问题专题、二叉树路径问题专题）。
  • 核心输出 ：整理各类算法的思维导图或笔记，记录经典题型的“解题模板”和易错点。

• 第三个月：综合模拟与弱点突破期（约28题）

  • 目标 ：进行整套题的模拟练习，控制时间（通常机试是2-3小时3题）。重点回顾前两个月的错题和难题。
  • 每日/每周任务 ：每周进行2-3次限时模拟。针对模拟中暴露的弱点（如DFS写错、DP状态定义不清），进行专题强化。
  • 核心输出 ：形成自己的“错题本”，分析每道错题的原因（是思路错误、边界条件、语法错误还是时间复杂度过高？）。

4.2 实操心法：不止于AC的深度练习

1. 五步刷题法 ：

   • 读题与抽象 ：仔细读题，明确输入输出格式、数据范围、边界条件。将实际问题抽象为数据结构与算法问题。
   • 思考与设计 ：不急于写代码！先用自然语言或伪代码描述思路。思考时间与空间复杂度，评估是否满足要求。这是锻炼算法思维的关键。
   • 编码实现 ：将思路转化为C++代码。注意代码风格、变量命名、模块化（将独立功能写成函数）。
   • 调试与测试 ：用题目给的样例、自编的边界样例（如空输入、极值）进行测试。善用IDE的调试功能，单步跟踪变量变化。
   • 复盘与优化 ：AC（Accept）不是终点。查看题解区，学习更优的解法。思考自己的解法哪里可以优化？是否有未考虑的边界情况？将心得记录下来。

2. 调试技巧 ：

   • “小黄鸭”调试法 ：向别人（或一只玩具鸭）一行行解释你的代码逻辑，往往在解释过程中就能发现错误。
   • 打印中间变量 ：在关键步骤后打印变量值，这是最直接有效的调试手段。
   • 构造极端用例 ：针对数组，考虑空数组、单元素、全部相同、已排序、逆序等情况。针对树，考虑空树、单节点、链状树（退化成链表）。

3. 时间与空间复杂度分析 ：

   • 养成习惯，在代码注释开头简要写出算法的时间复杂度和空间复杂度。这是面试中必问的环节。
   • 理解常见操作的时间复杂度： vector 尾部插入O(1)，中间插入O(n)； unordered_map 查找平均O(1)； sort 是O(n log n)。

4.3 环境与工具准备

• 本地IDE ：推荐使用Visual Studio Code (VSCode) 或 CLion。VSCode轻量，配置C++环境（安装MinGW或使用WSL，配置C/C++插件）后非常方便。CLion功能强大，对C++支持更完善，但相对较重。
• 在线判题平台（OJ） ：除了在本地练习，必须在OJ上提交代码，适应其严格的输入输出和时空限制。国内常用的有 牛客网 （有华为机试真题专区）、 力扣（LeetCode） 、 AcWing 等。力扣的题目分类和讨论区质量很高，非常适合学习。
• 代码管理 ：使用GitHub或Gitee管理你的刷题代码库。为每道题建立独立的文件，并附上解题思路的README。这既是备份，也是你学习历程的宝贵记录。

坚持这套方法三个月，你收获的将不仅仅是108道题的答案，更是一套解决未知算法问题的系统性思维方式和熟练的C++工程实践能力。这远比单纯背题要重要得多。在接下来的具体题目解析中，我将贯穿这些心法，带你一道一道地攻克难关。