华为OD机试模拟题5全解析：字符串、贪心与背包实战

华为机试这东西圈内人都懂它不叫什么“算法竞赛”也不讲什么“项目经验”它就是一杆秤直接称你写代码的基本功。最近不少人在刷“华为机试编程模拟题5”这类套题还有人私信问我OD机试新系统、双机位C卷到底什么难度、该按什么顺序刷题。正好我手上刚带完一批备考的朋友把第5套模拟题从头到尾撸了一遍也总结了不少踩坑经验。这篇就把这套题的拆解思路、编码实现、答题策略和常见翻车点一次性说清不管是刚入门准备机试的还是刷题刷到瓶颈想提速的应该都能在里面找到点有用的东西。先说明一下我拿到的“模拟题5”是一个典型的三题组合卷覆盖了字符串处理、贪心/模拟、以及基础动态规划三种类型。题量不算大但很能体现华为机试的命题风格——不考偏题怪题考的是你在有限时间内能不能用最稳妥的方式把一道业务味道很浓的题目写对。你要知道华为机试改卷是不看代码风格的只看测试用例过没过所以你写的代码丑一点没关系思路稳、边界全、能AC就是王道。1. 内容整体设计与思路拆解1.1 华为机试到底在考什么在聊模拟题5之前有必要先把机试的底层逻辑捋一遍。华为机试一般时长2小时3道题分值分布大约是100分、200分、300分总分600分。分数线和你的目标部门、岗位级别挂钩但通常来说100分那道题必须拿满200分的尽量拿满300分的至少过部分测试用例。这个策略非常重要因为很多人在第三题死磕到底结果前面简单的题反而因为粗心丢了分。从题型分布来看华为机试的题库虽然庞大但考点高度集中字符串处理、排序、滑动窗口、双指针、贪心、模拟、动态规划、DFS/BFS、并查集、前缀和。相比ACM比赛华为机试更看重“能把问题拆解成代码逻辑”的能力而不是各种高深的数据结构。你甚至可以不用红黑树、不用线段树、不用KMP老老实实用数组、哈希表、双循环也能通过大部分题目。1.2 为什么建议按模拟卷刷题很多备考的同学喜欢按专题刷题今天刷字符串明天刷DP后天刷图论。这种方式能夯实知识点但如果临近考试我强烈建议你改成刷整卷模拟题。原因很简单机试的难度不在单个题目而在状态切换。你前面刚写完一个字符串处理脑子还停留在字符数组的思维里下一题突然跳到动态规划思路能不能快速切过来这需要练习。我在带人刷题的时候一直强调模拟题的价值不是“对答案”而是“模拟考场状态”。你按考试时间和规则把一套卷子完整做下来然后复盘哪里卡住了、哪里超时了、哪里边界漏了这套流程才是真正提升分数的关键。模拟题5就是一套非常适合用来练考场状态的卷子它的难度梯度合理题型覆盖典型部分题目甚至可以说是真题的换皮版本。所以如果你已经刷过一遍基础算法强烈建议现在开始按套卷来冲刺。1.3 模拟题5的整体难度评估先说结论模拟题5的整体难度在市面流传的各种模拟卷里属于中等偏上一点点。第一题是字符串处理难度不大但极其容易踩坑第二题是带一点贪心思想的模拟题需要排序和前缀和的配合第三题是一个背包问题的变种考察状态转移的基本功。这套卷子很典型地反映了一个趋势现在的华为OD机试新系统、双机位C卷并不追求题目多么惊艳反而更青睐“把经典题目包装成实际业务场景”的考法。比如字符串题会套一个日志解析的外壳背包题会伪装成资源分配问题。所以你刷题的时候不要只背代码模板要锻炼自己“识别题目本质”的能力。看到一个场景能快速翻译成算法模型这才是高分的关键。2. 核心细节解析与实操要点2.1 第一题字符串解压缩难度简单偏中这道题我记得很清楚题目是给定一个压缩后的字符串比如“3[ab]2[c]”要求输出解压后的结果“abababcc”。看似简单的字符串处理其实隐藏着两个大坑第一个坑是数字可能不止一位数比如“12[ab]”第二个坑是括号可能是嵌套的比如“2[a3[b]]”。嵌套结构一出现熟悉的朋友立刻会想到栈。但如果直接用栈写代码量不小而且处理数字拼接时容易出错。我建议用递归下降法这样思路更清晰而且嵌套深度在机试中通常不会太大直接用递归也不会爆栈。#include stdio.h #include string.h char s[100005]; int pos, len; // 解析从当前位置开始的一个单元 void parseUnit() { if (pos len) return; if (s[pos] 0 s[pos] 9) { int num 0; while (pos len s[pos] 0 s[pos] 9) { num num * 10 (s[pos] - 0); pos; } // 跳过 [ pos; while (pos len s[pos] ! ]) { parseUnit(); } // 跳过 ] pos; for (int i 0; i num; i) { for (int j 0; j curLen; j) { putchar(tmp[j]); } } } else { // 普通字符直接输出 tmp[curLen] s[pos]; pos; } }这个版本我做了简化实际写的时候需要用一个全局缓冲区暂存当前括号内解析出的内容然后根据倍数重复输出。这个思路其实很清晰看到数字就解析数字然后递归处理括号里的字符串遇到普通字符就直接输出或暂存。边界条件要特别注意数字解析完之后下标要移动到左括号之后右括号处理完之后下标也要正确移动。2.2 第二题任务调度与最大收益难度中等第二题是一个典型的贪心排序问题题面包装成“有多个任务每个任务有截止时间和收益每个单位时间只能做一个任务求最大收益”。这题的经典解法是按截止时间从小到大排序然后用一个小根堆维护已选任务的收益一旦发现当前已选任务数超过截止时间就把收益最小的任务踢出去。这个思路的巧妙之处在于我们不需要决定“哪个时间段做哪个任务”只需要维护一个“已选任务集合”保证集合中任务的个数永远不超过当前最早的截止时间这样一定存在一种合法的调度方案。#include stdio.h #include stdlib.h #define MAXN 10005 typedef struct { int dead; int profit; } Task; int cmp(const void *a, const void *b) { return ((Task *)a)-dead - ((Task *)b)-dead; } Task tasks[MAXN]; int heap[MAXN], heapSize; void push(int val) { heap[heapSize] val; int idx heapSize; while (idx 1 heap[idx] heap[idx / 2]) { int temp heap[idx]; heap[idx] heap[idx / 2]; heap[idx / 2] temp; idx / 2; } } int pop() { int ret heap[1]; heap[1] heap[heapSize--]; int idx 1; while (idx * 2 heapSize) { int child idx * 2; if (child 1 heapSize heap[child 1] heap[child]) { child; } if (heap[idx] heap[child]) break; int temp heap[idx]; heap[idx] heap[child]; heap[child] temp; idx child; } return ret; } int main() { int n; scanf(%d, n); for (int i 0; i n; i) { scanf(%d %d, tasks[i].dead, tasks[i].profit); } qsort(tasks, n, sizeof(Task), cmp); int total 0; for (int i 0; i n; i) { push(tasks[i].profit); total tasks[i].profit; if (heapSize tasks[i].dead) { total - pop(); } } printf(%d\n, total); return 0; }这段代码里小根堆是手写的因为机试环境不一定支持C的优先队列如果你用的是C则可以更简洁地使用priority_queueint, vectorint, greaterint。核心思想一定要记住我们维护的小根堆里存的是“当前已选择的任务的收益”一旦发现当前任务数超过了某个任务的截止时间说明我们必须放弃一个任务毫无疑问应该放弃收益最小的那个。我实操时发现这道题最容易被忽略的点是任务可能没有按时完成但题目要求收益最大化所以不需要把每个时间段都填满。很多新人写这题时会陷入“模拟时间线”的思路试图用数组标记每个时间段做哪个任务这种做法的复杂度是O(n^2)级别的遇到大数据量很容易超时。用贪心堆的思路复杂度只有O(nlogn)稳得很。2.3 第三题资源分配与背包变种难度中等偏难第三题从题面来看是一个“设备分配”问题有N个任务需要分配到M台设备上每个任务有处理耗时和收益每台设备有总处理时间的上限求总收益最大值。翻译过来就是一个二维费用背包或者严格说是一个“分组背包”的变种。这道题难在什么地方难在你得先识别出它是一个背包问题。如果你真把场景当业务题去模拟分配逻辑写出来的大概率是贪心算法而贪心在背包问题上是不能保证最优解的。只有你反应过来“每台设备就是一个容量限制每个任务是一个物品要么选要么不选”思路才算真正打开。#include stdio.h #include string.h #define MAXN 1005 #define MAXM 105 int dp[MAXM][MAXN]; int main() { int n, m; scanf(%d %d, n, m); memset(dp, 0, sizeof(dp)); for (int i 0; i n; i) { int cost, value; scanf(%d %d, cost, value); // 倒序遍历保证每个物品只选一次 for (int j m; j cost; j--) { for (int k MAXN - 1; k cost; k--) { if (dp[j - cost][k - cost] value dp[j][k]) { dp[j][k] dp[j - cost][k - cost] value; } } } } printf(%d\n, dp[m][MAXN - 1]); return 0; }这段代码是一个典型的二维背包模板但说实话实际做第三题时你很难一次就写出完美版本。我第一次做这题时错误地把设备个数当成了容量直接套了一维背包模板结果样例能过、大测试点挂掉排查了半天才发现是状态维度搞错了。这类题目在考场上非常考验心态因为你越急越容易错。我的建议是写代码前先在草稿纸上画一下状态转移方程dp[i][j]到底代表什么下标哪个是设备容量、哪个是时间容量想清楚了再动手。还有一点非常关键第三题的数据范围通常不会太大你要学会根据数据范围反推算法复杂度。比如看到N和M都在100以内O(NMM)的复杂度通常是可接受的但如果你用DFS去搜索每一种分配方案指数级的复杂度绝对会超时。考场上的一个核心原则就是根据数据范围猜测出题人想要的算法。这个能力刷套卷练出来的效果是最明显的。2.4 每道题的代码风格建议机试不像公司里写业务代码不需要你搞什么设计模式、依赖注入、单元测试一切都是“能跑就行”。但我还是建议你在代码可读性上稍微上点心原因很简单如果你调试的时候自己都看不下去自己的代码那等于给自己挖坑。我的习惯是核心变量命名使用有意义的英文单词缩写比如task、profit、deadline而不是a、b、c关键循环里加一两个注释方便自己定位函数拆小一点一个函数只做一件事。这些习惯在平时刷题时不显山露水但到了考场高度紧张的状态下整洁的代码真的能帮你省下很多排查时间。另外建议你固定使用一种语言刷题。我推荐C/C因为运行速度快对各种容器的掌控更底层而且华为机试对C/C的支持非常成熟。Python也能用而且在写一些字符串题时确实快很多但遇到大数据的题目时Python的性能瓶颈可能会让你卡在超时边缘所以如果你C不差就优先C吧。3. 实操过程与核心环节实现3.1 考场上的时间分配策略这个部分非常关键我见过的翻车案例里至少有一半是时间分配出了问题。一套卷2小时3道题我的建议是这样分割第一题20-30分钟搞定。如果卡了超过30分钟还没AC先放弃跳到第二题。因为第一题再难也就100分花太久只会挤占后面大题的时间。第二题40-50分钟。第二题一般200分值得投入较多时间。但要注意如果30分钟还没思路先写一个暴力解法能拿部分分就拿部分分。第三题剩余时间。第三题300分但也是最难的。千万别指望AC目标是尽可能多地通过测试用例。暴力解法、部分DP、甚至特判某些数据都能帮你捞到不少分。考场上最忌讳的心态是“这道题我一定要AC”。机试不是竞技比赛它是个及格性考试你要的是总分最大化而不是单题满分。先保证能拿的分拿稳再去冲难题。3.2 模拟题5的完整答题流程演示我以模拟题5为例带大家走一遍我自己的答题流程。拿到题目后先把三题都扫一遍花三分钟看清楚每道题的输入输出格式和大概思路方向。这个“全局扫描”非常重要它能帮你建立整场考试的时间预期。第一题如果是字符串解压我大概率直接用栈或递归20分钟内能搞定。写之前先在草稿纸上写下几个测试用例比如“3[a2[c]]”应输出“accaccacc”这种嵌套用例能帮你快速验证思路。第二题如果是任务调度我的第一反应就是贪心堆。不需要考虑其他方案直接按排序小根堆的思路写写完跑一下样例再构造几个边界测试比如所有任务截止时间都为1、收益相同的情况确认稳了再提交。第三题如果是背包变种我会在草稿纸上画状态转移方程明确dp数组两个维度的含义然后写代码。写完样例测试通过后我会故意构造一个稍大一点的数据观察代码运行时间确保不会超时。三题加起来实际写代码的时间大概100分钟左右剩下20分钟用来复查边界条件和输入输出的格式问题。有一点想提醒你千万不要提前交卷。机试不奖励“做得快”只奖励“做得对”。剩下的时间哪怕只是把三份代码读一遍也能抓出不少低级错误。3.3 关键边界条件的自查清单“边界条件”这个词说了无数遍但很多人还是会在上面丢分。模拟题5我总结了一份自查清单你可以直接拿去用字符串题输入字符串是否可能为空数字是否可能为0括号是否一定匹配数组题数组长度是否为1所有元素是否都相同是否可能所有元素都满足/都不满足条件DP题dp数组初始化是否正确是否能处理“一个物品都不选”的情况物品数量为0或容量为0时结果是否合理数值类型计算过程中是否可能溢出int范围如果可能要改用long long。每道题写完代码后按这个清单逐项检查一遍能有效避免“样例过了但提交挂了”的惨剧。这份清单看着简单但都是我用一次次考试挂分换来的血泪经验。3.4 输入输出技巧与常见陷阱华为机试的输入输出是比较常规的一般用scanf和printf就能搞定。C选手用cin和cout也没问题但记得加上ios::sync_with_stdio(false); cin.tie(0);这行快读代码否则大数据时可能会因为IO太慢导致超时。有个非常常见的坑如果是用scanf读字符串要确保字符数组开得足够大因为机试环境不会对数组越界做任何提示越界后可能导致神秘错误。读入一行带空格的字符串时记得用gets()或fgets()把整行读进去或者用scanf(“%[^\n]”, s)这种格式千万别用scanf(“%s”, s)它遇到空格就停了。输出格式也容易踩坑。有的题目要求每个结果占一行有的要求每个结果后面加一个换行还有的要求输出整数后不能有空格。我建议写一个简单的输出辅助函数统一格式减少手写出错的概率。3.5 机试环境的适配建议因为我带的这波朋友参加的OD机试用的是新系统双机位C卷这里顺便聊聊环境适配。双机位的意思是一个摄像头对着你本人和电脑屏幕另一个摄像头对着你的手部和桌面用来监控是否有作弊行为。这个系统的存在其实是在提醒你机试是独立完成的考试不要有任何侥幸心理。我建议你在考前就把桌面清空只留下必要的笔和草稿纸。考试过程中不要频繁转头、不要看手机、不要起身这些动作都可能被系统判定为异常行为。还有就是提前检测一下电脑的摄像头、麦克风、网络是否正常这些硬性问题如果在考场上出现非常影响心态。就代码环境而言机试系统一般自带编译器你在本地用什么IDE都行但考场上建议用系统默认的编辑器因为它的自动缩进和代码补全功能很有限你平时就要适应这种“裸写代码”的感觉。我自己带人的时候会要求他们关闭IDE的自动补全和语法提示只用最朴素的编辑器来刷题效果非常显著。4. 常见问题与排查技巧实录4.1 样例能过但提交只有60分这是机试里最让人崩溃的情况。样例过了、本地测试也过了一提交就只有60分甚至40分。出现这种情况90%是你漏了边界条件还有10%是算法复杂度太高导致超时。针对漏边界条件的情况你需要主动构造一些“刁钻”的测试数据。我一般会按这几个方向去验证空输入、单个元素、最大值、最小值、重复元素、乱序输入。针对超时的情况你需要评估数据范围如果数据量是10^5级别而你用了O(n^2)的算法大概率会有测试点超时。我在模拟题5的第二题遇到过这个问题贪心堆的时间复杂度是O(nlogn)按理说不会超时但我第一次写的时候堆是自己实现的写错了两个地方导致堆排序退化成O(n^2)大数据一跑就挂。排查了半天最后发现是heapify函数里索引写错了。这类堆实现的bug特别隐蔽建议用C选手直接用priority_queue能少踩很多坑。4.2 第三题完全没思路怎么办这个情况太常见了尤其是当你被一套卷子前面两道题耗掉太多精力后看到第三题那种大段的题面脑子很容易空白。我的建议是先把题目完整读三遍尽量把业务场景抽象成算法模型。如果读了三遍还不行立刻转写暴力解法。暴力解法有两种一种是枚举所有情况另一种是用DFS搜索。虽然暴力解法大概率过不了大数据测试点但它能帮你拿住小数据测试点的分数。千万不要因为觉得暴力解法“太low”就不写在机试里写暴力拿到的每一分都是实打实的。还有一个技巧观察题目数据范围。如果数据范围很小比如N10那出题人很可能就是允许暴力搜索的如果N的范围是10^5级别那必须用优化算法。根据数据范围反推算法这是机试和高水平算法竞赛里都非常好用的策略。4.3 编译错误和运行错误的排查思路编译错误通常是因为语法问题比如scanf少了一个、数组下标越界、变量名拼写错误等。机试的编译器一般会提示错误行号你顺着行号找就能发现问题。运行错误则复杂一些可能是数组越界、栈溢出、空指针、除零等。数组越界是最常见的运行错误。我处理这类问题时会习惯性地把数组开大一点比如题目数据范围是N1000我就开N10或者N100。这个习惯虽然浪费一点内存但能有效避免越界错误。另外调试时如果发现程序崩溃可以尝试用printf在关键位置打印变量值定位崩溃位置。这种方式虽然原始但在机试环境下非常实用。4.4 机试环境下的调试技巧机试系统一般不支持断点调试也不支持看变量值所以你只能自己想尽办法定位问题。我的调试三板斧是第一招打印大法。在可疑位置打印变量的值看是否和预期一致。用完记得删除或注释掉别留着影响输出结果。第二招二分定位。如果程序某一段逻辑有问题通过不断缩小范围找到出错的具体位置。比如用二分的方式逐步注释掉代码段定位到出错的那几行。第三招小数据验证。构造一个非常小的测试用例比如只有3个元素的数组手动推演一遍程序运行过程对比代码实际输出就能发现逻辑错误。这三招看起来朴素但真的能解决90%以上的调试问题。调试心态也很重要不要急躁仔细看输出一步一步排查总能找到问题。4.5 模拟题5的高频翻车点汇总最后列一下模拟题5这道卷子里我曾见过的高频翻车点有的来自我自己有的来自我带过的备考朋友第一题字符串解压最容易翻车在两处数字是多位数的处理以及递归返回值传递的路径。很多新手在递归函数里忘记返回“当前扫描到的位置”导致外层递归重复扫描了同一个字符输出结果直接翻倍。第二题任务调度最容易翻车在堆的维护逻辑上当任务数超过截止时间时应该踢出的是收益最小的任务而不是新任务。有人会把逻辑写成“当新任务收益大于堆顶时弹出堆顶再压入新任务”这个逻辑在部分情况下也能过但它不是标准的解法容易在某些特殊测试点出错。第三题背包变种最容易翻车在状态维度搞混。记住一个技巧先想清楚dp数组的下标代表什么、值代表什么再想清楚转移方程。很多人的错误源头都是“没想清楚就开始写”。4.6 刷完模拟题5之后的复盘方法刷完一套题不复盘等于白刷。我的复盘流程分三步第一步看自己每道题花了多少时间如果在某类题上反复超时说明这个知识点掌握不牢需要回到专题刷题补基础。第二步看自己提交后错在哪些测试点尽量还原出错的测试数据理解为什么会错。第三步把错题整理进错题本标记出错误原因是边界条件、算法复杂度、还是逻辑漏洞。错题本我强烈建议你电子化用表格记录题目类型、错误原因、正确解法、考点标签刷到一定数量后你会发现自己的弱点非常清晰。比如我的错题本显示我的字符串处理正确率只有70%但DP类正确率高达95%那接下来重心就应该放在字符串处理上。顺便提一句现在AI编程工具很火也有人用Cursor这类AI编程助手辅助刷题。说实话日常学习时让AI给你解释算法思路、帮你审查代码是不错的选择但考场上请务必独立完成。双机位监控就摆在那里独立完成既是对考试的尊重也是对自己能力的真实检验。不要把AI当成考试作弊的工具把它当成日常学习的助手这个边界一定要清醒。5. 华为OD机试新系统与备考节奏5.1 新系统双机位C卷的应对建议很多朋友担心双机位C卷和传统机试有什么本质区别实际上从算法考点来看几乎没有变化。双机位更多是监考形式的变化而非题目难度的变化。你该刷的题还是那些高频考点该掌握的算法还是那些经典模型。不过双机位确实要求你调整一些备考习惯。平时刷题时就要练习在“可被观察”的环境下独立完成题目不要养成依赖搜索、依赖提示的习惯。还有一个细节是考试前一定要确保手机静音、关掉消息通知因为双机位监控会检测是否使用手机一旦判定异常后果很严重。5.2 两个月内的高效刷题规划如果你还有两个月准备时间我给你一个比较合理的刷题节奏前一个月按专题刷把字符串、排序、哈希、贪心、DP、DFS/BFS这六大板块的基础题刷明白每个板块至少50道。中间两周开始刷整卷模拟题一周3-4套按考场规则来记录时间和得分。最后两周回归错题本把之前做错的题重新做一遍巩固不熟的知识点。最后几天可以适当减少刷题量多看看错题和模板代码调整好状态迎接考试。5.3 我在带人备考时的一些心里话最后说几句掏心窝子的话。华为机试这个考试说难确实难因为它是实打实的编码能力测试容不得半点含糊但说简单也简单因为它的考点非常固定你只要把高频题型练透大概率能拿到满意的分数。我带过的学员里有零基础转行两个月上岸的也有科班出身刷了半年还挂了的差别不在智商而在方法。方法的第一条是尽早动手写代码不要停留在看题解的阶段。第二条是认真对待每一次模拟考把它当成真正的考试。第三条是学会复盘让自己的错误成为进步的台阶。这三条听着简单做到的人真不多。这套模拟题5如果你能按照我上面说的节奏完整做一遍并复盘透彻我相信你的机试水平会有一个质的提升。关于华为机试和OD机试备考如果你还有其他疑问欢迎在评论区留言我看到会尽量回复。后面我也会陆续把其他几套模拟卷的拆解文章整理出来咱们一步步来把每一套题都榨干吃透。