2026年7月 华为 研发岗 笔试试题及分析

2026-7-15 华为研发岗笔试试题

考察内容涉及：双指针，单调栈，深搜（DFS）以及简单DP

第一题-水槽存水

时间限制： 1000ms  空间限制： 256M

题目描述

有一条直线水槽，左右两端始终开口（无挡板，水可从两端流走），水槽中从左到右插入了  块竖直挡板，第  块挡板高度为  （挡板厚度忽略不计）。 相邻两块挡板之间形成一个槽位（槽底面积为 1），一共存在  个槽位。 近期持续下雨，每个槽位都能接收到充足的雨水，直到水面稳定。 对于槽位  （挡板  与  之间）由于槽底面积为 1，故槽位的存水量数值等于其水面高度（如果只有一个挡板则无法形成槽位，其存水量为 0）。 如下图所示，5 块挡板形成 4 个槽位，以槽位 3 的存水量计算为例，槽位 3 的水面高度受挡板 2 （高度 2 ）和挡板 5 （高度 5 ）影响，水面高度为 2 ，故槽位 3 的存水量为 2 。

图中红色竖条为挡板，条顶数字是挡板高度，蓝色区域为水面稳定后各槽位的存水，块内数字是该槽位的水面高度。

输入描述

第一行一个整数  ，表示挡板个数。 第二行  个整数  ，表示从左往右的每个挡板高度。

输出描述

一个整数，输出水槽水面稳定后所有槽位的总存水量。

样例1

输入

51 2 3 4 5

输出

10

这道题是经典的“接雨水”问题（Trapping Rain Water）的变体。

题目分析

1. 物理模型：

• 水槽左右两端开口，意味着水会从两边流走，只有被挡板围住的区域才能存水。
• 对于任意一个槽位（两个相邻挡板之间），其存水高度取决于它左侧最高挡板和右侧最高挡板中较矮的那个（木桶效应）。
• 如果左侧或右侧没有比当前槽位更高的挡板，水就会流走，存水量为 0。

2. 算法选择： 题目描述的是  块挡板形成  个槽位。

• 挡板高度为 。
• 槽位  位于  和  之间。
• 槽位  的水位高度 。即：该槽位左侧所有挡板的最大值与右侧所有挡板的最大值取较小者。
• 槽位  的存水量 = （因为题目说槽底面积为1，且没提槽位本身有高度阻挡，除了两边的挡板）。注意：如果算出的水位低于两边挡板的较高者是不可能的，但根据物理原理，水位不可能低于 。实际上公式  已经隐含了这一点，因为  且 。

3. 计算步骤：

• 左侧最高挡板 = pre_max[i]
• 右侧最高挡板 = suf_max[i+1]
• 当前槽位水位 = min(pre_max[i], suf_max[i+1])
• 累加水位到总结果。
• 读取  和数组 。
• 构建前缀最大值数组 pre_max：pre_max[i] 表示  到  的最大值。
• 构建后缀最大值数组 suf_max：suf_max[i] 表示  到  的最大值。
• 遍历每一个槽位 （从 0 到 ）：

C++ 代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){    ios_base::sync_with_stdio(false);cin.tie(NULL);int n;if (!(cin >> n)) return0;// 如果只有1块或0块挡板，无法形成槽位if (n <= 1) {cout << 0 << endl;return 0;    }vector<int> h(n);for (int i = 0; i < n; ++i) {cin >> h[i];    }// pre_max[i] 存储从 h[0] 到 h[i] 的最大值vector<int> pre_max(n);    pre_max[0] = h[0];for (int i = 1; i < n; ++i) {        pre_max[i] = max(pre_max[i - 1], h[i]);    }// suf_max[i] 存储从 h[i] 到 h[n-1] 的最大值vector<int> suf_max(n);    suf_max[n - 1] = h[n - 1];for (int i = n - 2; i >= 0; --i) {        suf_max[i] = max(suf_max[i + 1], h[i]);    }long long total_water = 0;// 遍历所有槽位，槽位 i 位于挡板 i 和 i+1 之间for (int i = 0; i < n - 1; ++i) {int water_level = min(pre_max[i], suf_max[i + 1]);        total_water += water_level;    }cout << total_water << endl;return 0;}

复杂度分析

• 时间复杂度：。需要三次线性扫描（一次计算前缀，一次计算后缀，一次计算结果），满足 1000ms 的限制。
• 空间复杂度：。使用了两个辅助数组存储前缀和后缀最大值。

双指针（Two Pointers）解法：

#include<bits/stdc++.h>using namespace std;intmain(){    ios_base::sync_with_stdio(false);cin.tie(NULL);int n;if (!(cin >> n)) return 0;if (n < 2) {cout << 0 << endl;return 0;    }vector<int> h(n);for (int i = 0; i < n; ++i) {cin >> h[i];    }long long total_water = 0; int left = 0;              // 左指针，指向左边的挡板int right = n - 1;         // 右指针，指向右边的挡板int left_max = 0;          // 记录左边遇到的最高挡板int right_max = 0;         // 记录右边遇到的最高挡板// 当左指针在右指针左侧时循环while (left < right) {// 更新当前的左右最大值        left_max = max(left_max, h[left]);        right_max = max(right_max, h[right]);// 哪边低，哪边就是瓶颈if (left_max < right_max) {            total_water += left_max;            left++; // 处理完这个槽位，左指针右移        } else {// 右边低（或相等），说明 right-1 和 right 之间的槽位水位受限于 right_max            total_water += right_max;            right--; // 处理完这个槽位，右指针左移        }    }cout << total_water << endl;return 0;}

此外，使用单调栈（Monotonic Stack） 是解决“接雨水”问题的另一种经典方法。

核心思路

1. 原理： 积水总是发生在“低洼”地带。当我们从左向右遍历时，如果遇到的挡板高度是递增的，水会流走；只有当遇到一个比当前栈顶更高的挡板时，才可能形成一个“坑”，从而产生积水。

2. 栈的维护： 我们维护一个单调递减栈，栈中存储的是挡板的下标。

• 新的栈顶元素即为左边界（Left）。
• 当前遍历到的 i 为右边界（Right）。
• 这就形成了一个可以存水的区域。
• 如果当前挡板高度 h[i] 小于等于栈顶挡板高度，说明还没形成右边界，直接入栈。
• 如果当前挡板高度 h[i] 大于栈顶挡板高度，说明找到了一个右边界。此时弹出栈顶元素作为底部（Bottom）。

3. 水量计算：

• 宽度：width = i - left_index - 1（右边界下标 - 左边界下标 - 1）。
• 高度：bounded_height = min(h[i], h[left_index]) - h[bottom_index]（左右边界较矮者 - 底部高度）。
• 当前层积水量：width * bounded_height。
• 循环弹出并计算，直到栈为空或栈顶高度大于当前高度。

C++ 代码实现

#include<bits/stdc++.h>using namespace std;intmain(){    ios_base::sync_with_stdio(false);cin.tie(NULL);int n;if (!(cin >> n)) return 0;if (n < 2) {cout << 0 << endl;return 0;    }vector<int> h(n);for (int i = 0; i < n; ++i) {cin >> h[i];    }long long total_water = 0;stack<int> st; // 存储下标的单调递减栈for (int i = 0; i < n; ++i) {// 当前高度大于栈顶高度时，说明找到了右边界，可以开始计算积水while (!st.empty() && h[i] > h[st.top()]) {int bottom_idx = st.top(); // 底部（洼地）的下标            st.pop();                  // 弹出底部// 栈空，说明左边没有挡板了，无法形成闭合区域，水会流走if (st.empty()) break;int left_idx = st.top(); // 左边界下标// 宽度：右边界下标 i - 左边界 - 1long long width = i - left_idx - 1;// 计算有效高度：min(左边界高, 右边界高) - 底部高long long height = min(h[left_idx], h[i]) - h[bottom_idx];// 累加这一层的横向积水量            total_water += width * height;        }// 将当前下标入栈，维持单调递减性质        st.push(i);    }cout << total_water << endl;return 0;}

复杂度分析

• 时间复杂度：。虽然代码中有双重循环（for 里面套 while），但每个元素最多只会被入栈一次和出栈一次，所以总操作次数是线性的。
• 空间复杂度：。最坏情况下（例如挡板高度单调递减），栈中需要存储  个元素。

第二题-手机多载波冲突选择

时间限制：1000ms 空间限制：256M

题目描述

在手机通信中，为了提升网速，基站可以同时使用多个频段（称为载波聚合），每个频段提供一定的带宽，但存在以下限制：每个频段最多选一个载波（不能同时选择同一频段的多个载波）；冲突频段不能同时使用（如 n1 和 n2 冲突，只能选其中一个）；最多选择  个载波（可以少于 ）。

你的任务是：选择一组载波，使得总带宽最大，同时满足上述约束；输出最大总带宽，并给出所选载波的编号。

输入描述

第一行两个整数 ，其中  表示载波总数， 表示最多选  个载波。

第二行  个整数 ，表示每个载波的带宽。

第三行  个字符串 ，表示每个载波所属的频段，为 n 开头的字符串，如 n1、n2，不区分大小写，字符串长度不超过 10。

第四行一个整数 ，表示冲突频段对数。

接下来  行，每行两个频段 ，表示  和  不能同时选（冲突关系不传递）。

输出描述

第一行输出最大总带宽。

第二行输出所选载波的编号（从 0 开始，按升序排列，数值序最小；组合有多种时，则输出数值序最小的一组）。

样例 1

输入

6 2100 200 150 300 250 180n78 n41 n78 n28 n41 n281n28 n41

输出

4502 3

问题分析

这是一个典型的带约束的组合优化问题。 需要从  个载波中选择最多  个，使得总带宽最大。 约束条件如下：

1. 频段互斥：同一个频段（如 n78）只能选一个载波。
2. 冲突互斥：给定的冲突频段对（如 n28 和 n41）不能同时被选中。
3. 数量限制：选中的载波数量不能超过 。
4. 字典序最小：如果最大带宽有多种组合，输出载波编号字典序最小的那一组。

算法选择

由于  且 ，直接暴力枚举所有组合  约为 100 万次，这在计算时间上是可行的。可以使用 回溯法（DFS） 来搜索解空间。

为了保证输出结果的字典序最小，在搜索时采用以下策略：

• 搜索顺序：按载波编号从小到大（0 到 N-1）进行搜索。
• 剪枝与更新：当我们找到一个总带宽更大的方案时，更新最优解。由于我们是按编号从小到大搜索的，且只有在“严格大于”当前最大带宽时才更新，因此第一个找到的最大带宽组合自然就是字典序最小的。

C++ 代码实现

#include<bits/stdc++.h>using namespace std;int N, K, C;vector<int> bandwidths;       // 存储每个载波的带宽vector<string> freqs;         // 存储每个载波的频段map<string, int> conflictMap; // 将频段名映射为整数ID，方便处理冲突vector<pair<int, int>> conflicts; // 存储冲突对的IDint maxTotalBandwidth = -1;   // 记录找到的最大带宽vector<int> bestIndices;      // 记录最优解的载波下标// 检查当前选择的载波集合是否合法// currentIndices: 当前已选择的载波下标列表// newIdx: 新尝试加入的载波下标boolisValid(constvector<int>& currentIndices, int newIdx){string newFreq = freqs[newIdx];// 检查同频段互斥for (int idx : currentIndices) {if (freqs[idx] == newFreq) {return false;        }    }// 检查冲突频段互斥int newFreqId = conflictMap[newFreq];for (int idx : currentIndices) {int existFreqId = conflictMap[freqs[idx]];// 检查 (newFreqId, existFreqId) 是否在冲突列表中for (constauto& p : conflicts) {if ((p.first == newFreqId && p.second == existFreqId) ||                (p.first == existFreqId && p.second == newFreqId)) {return false;            }        }    }return true;}// start: 当前搜索的起始下标// count: 当前已选择的载波数量// currentSum: 当前已选择的总带宽// path: 当前已选择的载波下标路径voiddfs(int start, int count, int currentSum, vector<int>& path){// 更新最优解if (currentSum > maxTotalBandwidth) {        maxTotalBandwidth = currentSum;        bestIndices = path;    }// 如果已选满 K 个，或者没有更多载波可选，停止深入if (count == K || start == N) {return;    }// 遍历剩下的载波for (int i = start; i < N; ++i) {// 尝试选择第 i 个载波if (isValid(path, i)) {            path.push_back(i);            dfs(i + 1, count + 1, currentSum + bandwidths[i], path);            path.pop_back(); // 回溯        }    }}intmain(){    ios_base::sync_with_stdio(false);cin.tie(NULL);if (!(cin >> N >> K)) return 0;    bandwidths.resize(N);    freqs.resize(N);for (int i = 0; i < N; ++i) cin >> bandwidths[i];for (int i = 0; i < N; ++i) {cin >> freqs[i];// 统一转为小写处理        transform(freqs[i].begin(), freqs[i].end(), freqs[i].begin(), ::tolower);    }cin >> C;int idCounter = 0;// 用于快速判断冲突vector<pair<string, string>> rawConflicts(C);for (int i = 0; i < C; ++i) {string a, b;cin >> a >> b;        transform(a.begin(), a.end(), a.begin(), ::tolower);        transform(b.begin(), b.end(), b.begin(), ::tolower);        rawConflicts[i] = {a, b};// 收集所有涉及冲突的频段并分配IDif (conflictMap.find(a) == conflictMap.end()) conflictMap[a] = idCounter++;if (conflictMap.find(b) == conflictMap.end()) conflictMap[b] = idCounter++;    }// 将字符串冲突转换为整数ID冲突for (constauto& p : rawConflicts) {        conflicts.push_back({conflictMap[p.first], conflictMap[p.second]});    }vector<int> path;    dfs(0, 0, 0, path);cout << maxTotalBandwidth << endl;for (int i = 0; i < bestIndices.size(); ++i) {if (i > 0) cout << " ";cout << bestIndices[i];    }cout << endl;return 0;}

复杂度分析：

• 最坏情况下，需要探索从 25 个数中选 8 个数的组合，即 。
• 对于每个组合，检查合法性的开销很小（最多检查 8 次）。
• 总运算量在百万级别，完全可以在 1000ms 的时间限制内完成。

第三题-字符补全

时间限制：1000ms  空间限制：256M

题目描述

给定一个目标字符串  和一个源字符串 ，请你找出需要在  中最少插入多少个字符（可以在任意位置插入），才能使得  成为  的子序列。

注意： 子序列定义：对于一个字符串 ，如果字符串  可以通过删除  中的一些字符（可以删除 0 个或多个，不改变剩余字符的相对顺序）得到，则称  是  的子序列。例如：在 acbd 中，ab、ac、ad、cd、abcd 等都是其子序列。子序列中的字符在原字符串中不需要连续出现，但必须保持原有的相对顺序。例如：ab 是 axby 的子序列，因为 a 在 b 之前出现。 只能插入字符，不能删除或修改现有字符。 插入的字符必须是  中有的字符。

输入描述

第一行输入目标字符串 。 第二行输入源字符串 。 其中  和  只包含小写字母 a ~ z，长度满足 。

输出描述

输出最少需要插入的字符数量。

样例1

输入

abcac

输出

1

这题是 最长公共子序列（LCS） 问题的变种。

核心思路

1. 问题转化： 题目要求在源字符串  中插入最少的字符，使得目标字符串  成为  的子序列。 这意味着  中原本已经包含的、且符合  中顺序的字符越多，我们需要插入的字符就越少。 因此，我们需要找到  和  的最长公共子序列（LCS）。

2. 计算公式：

• 设  为字符串  和  的最长公共子序列的长度。
• 这个长度代表了  中已经存在的、能直接匹配上  的最大字符数。
•  中剩余的字符（即  的总长度减去 LCS 长度）就是我们需要插入到  中的字符。
• 答案 = 

3. 动态规划求解 LCS： 定义 dp[i][j] 表示  的前  个字符和  的前  个字符的最长公共子序列长度。

• 如果 S[i-1] == T[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
• 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

C++ 代码实现

#include<bits/stdc++.h>using namespace std;intmain(){    ios_base::sync_with_stdio(false);cin.tie(NULL);string T, S;if (!(cin >> T >> S)) return 0;int lenT = T.length();int lenS = S.length();// dp[i][j] 表示 S 的前 i 个字符与 T 的前 j 个字符的 LCS 长度vector<vector<int>> dp(lenS + 1, vector<int>(lenT + 1, 0));for (int i = 1; i <= lenS; ++i) {for (int j = 1; j <= lenT; ++j) {if (S[i - 1] == T[j - 1]) {// 如果当前字符匹配，则 LCS 长度加 1                dp[i][j] = dp[i - 1][j - 1] + 1;            } else {// 如果不匹配，取左边或上边的最大值                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);            }        }    }// 最长公共子序列的长度int lcs_length = dp[lenS][lenT];// 需要插入的字符数 = 目标串长度 - 公共部分长度int result = lenT - lcs_length;cout << result << endl;return 0;}

复杂度分析

• 时间复杂度：。由于题目给定 ，计算量约为 ，完全可以在 1000ms 的限制内通过。
• 空间复杂度：，用于存储 DP 表。

这题用滚动数组还能把空间优化到 O(N)

1. 空间优化（滚动数组）：

• 原始解法使用二维数组 dp[N][M]，当字符串长度达到 2500 时，需要约  的内存。虽然未超过 256M 限制，但在算法竞赛或面试中，将其优化为  是更优的做法。
• 观察状态转移方程 dp[i][j] 仅依赖于上一行 dp[i-1][...] 和当前行 dp[i][...] 的左侧数据。因此，我们可以将二维数组压缩为一维数组。
• 在更新一维数组时，为了防止覆盖掉“左上角”的旧值（即 dp[i-1][j-1]），我们需要用一个临时变量 prev 来保存它。

2. 时间/常数优化：

• 确保遍历外层循环时选择较短的字符串作为列维度（虽然 LCS 对称，但配合滚动数组时，列越短，数组越小，Cache 命中率越高）。
• 使用 std::ios::sync_with_stdio(false) 加速 I/O。

优化后的 C++ 代码

#include<bits/stdc++.h>using namespace std;intmain(){    ios_base::sync_with_stdio(false);cin.tie(NULL);string T, S;if (!(cin >> T >> S)) return0;int lenT = T.length();int lenS = S.length();// 使用一维数组（滚动数组）// dp[j] 表示当前处理到 S 的某一位时，与 T 的前 j 位匹配的 LCS 长度// 大小设为 lenT + 1，即目标字符串长度 + 1vector<int> dp(lenT + 1, 0);for (int i = 1; i <= lenS; ++i) {int prev = 0; // prev 用于保存 "左上角" 的值 (对应 dp[i-1][j-1])for (int j = 1; j <= lenT; ++j) {int temp = dp[j]; // 暂存当前的 dp[j]，它是下一轮循环的 "左上角"if (S[i - 1] == T[j - 1]) {// 如果字符匹配：当前值 = 左上角旧值 + 1                dp[j] = prev + 1;            } else {// 如果不匹配：取 左边(dp[j-1]) 和 上边(旧的dp[j]) 的最大值// 注意：此时 dp[j] 还没被覆盖，代表的是上一行的值（上边）// dp[j-1] 已经被更新，代表的是当前行的值（左边）                dp[j] = max(dp[j], dp[j - 1]);            }            prev = temp; // 更新 prev 为旧的 dp[j]，供下一次内层循环使用        }    }// 需要插入的字符数 = 目标串总长度 - 最长公共子序列长度int lcs_length = dp[lenT];cout << (lenT - lcs_length) << endl;return 0;}

复杂度分析

• 时间复杂度：。这是计算 LCS 的理论下界，无法进一步降低，但常数更小。
• 空间复杂度：。我们只使用了一个长度为  的一维数组，相比原来的二维数组节省了约 99% 的空间（在本题数据规模下，从 25MB 降至约 10KB）。

在一维 DP 中，dp[j] 在被更新前存储的是上一行（）的数据，更新后存储的是当前行（）的数据。

• 当计算 dp[j] 时，我们需要 dp[i-1][j-1]。但在这一轮循环开始时，dp[j-1] 已经被更新成了 dp[i][j-1]。
• 因此，我们必须用变量 prev 在进入内层循环前或更新前“记住”那个被覆盖掉的旧值。