每年校招季和社招高峰期总有一批朋友被“华为机试/华为OD机试”这几个字折磨得睡不着觉。这套在线编程考试说难不算特别难说简单又处处是坑。作为经历过几轮机试、也帮不少同学review过模拟题的人我发现大家最容易出问题的不是算法本身而是对题目考点不熟、对输入输出处理大意、以及缺乏一套规范的模拟训练节奏。这篇文章我拿“华为机试编程模拟题5”这套题目当例子把整套题的拆解思路、每题的核心算法和代码实现、以及我踩过的那些坑系统性地过一遍。不管你是刚开始刷题想摸底还是考前冲刺查漏补缺都能从中找到可以直接照做的方案。全文我会用Python实现但算法思路对C/Java同样适用。1. 整套模拟题的设计思路与考点分布1.1 这套题背后想考察什么华为机试含OD机试的题目风格非常统一——不考偏题怪题核心就是数据结构、字符串处理、搜索/动规、边界条件处理这几板斧。它不像ACM那样要求你用奇技淫巧反而特别看重你把一个朴素解法写对、写稳、写清楚的能力。“模拟题5”这套卷子我整体看下来三题的难度梯度安排得很典型题号核心考点难度建议用时第一题字符串处理 滑动窗口/哈希统计简单15~20分钟第二题贪心 or 动态规划跳跃问题/区间问题中等30~35分钟第三题图论建模 拓扑排序/状态搜索较难40~50分钟这个梯度不是随便排的。第一题的价值是保底确保绝大多数人能拿到基础分第二题是分水岭考察你能否从“暴力解法”跨到“最优解法”第三题则是区分度题用来筛掉那些只会背题、不会建模的考生。1.2 华为机试的评测规则你需要提前摸清很多人在牛客网、力扣上刷题很顺一到华为机试就翻车核心原因是不熟悉它的OJOnline Judge模式。第一华为机试通常采用ACM模式也就是你需要自己处理输入输出。不像力扣那样给你封装好函数你只需要填函数体。机试要求你从标准输入流里读数据再按格式把结果打印到标准输出。这个习惯必须提前适应否则你写对了算法却因为输出格式不对被判零分。第二机试的输入用例经常带多组数据或者后缀空格等干扰项如果你只按一次性输入处理很容易WAWrong Answer。稳健的做法是读完整行再strip处理好空行。第三时间复杂度的限制通常是1~2秒内存限制在256MB或512MB。对Python来说O(n^2)在数据量到10^5级别时会非常危险所以平时练习就要有意识地算出复杂度上限。我见过很多人的代码思路对就是超时原因就是用了不必要的内层循环。这套模拟题5的每题我都会专门标注复杂度的红线你按这个标准去控制自己的代码。2. 第一题高频易错题字符串压缩与去重排序2.1 题目原型与考察逻辑第一题的典型场景是这样模拟题5略有变形但核心一致给定一个字符串里面包含大小写字母和数字。要求将字符串中连续出现次数 3的字符片段进行压缩压缩规则是“字符连续出现次数”。压缩完成后统计剩余字符中每个字符出现的次数按次数降序排列输出次数相同则按ASCII码升序排列。这类题看起来简单实际拿满分并不容易。它同时考察了字符串遍历、滑动窗口或双指针、排序规则定制三个基本功还埋了两个容易踩的坑压缩时是“边处理边统计”还是“先压缩再统计”如果顺序错了统计结果会被破坏。排序条件要处理“次数相同按ASCII升序”这种复合比较用Python的sorted配合lambda可以一行搞定问题不大但C里就要小心sort比较器的写法。2.2 我推荐的实现方案与代码我的思路分三步走用双指针遍历字符串找到每个连续字符片段。left指向片段起点right不断右移直到字符变化。如果片段长度 3就用charcount的形式拼进结果否则保留原字符。再遍历拼接后的结果字符串用字典统计次数最后按规则排序输出。import sys def compress_and_count(s: str) - str: if not s: return # Step 12双指针压缩 compressed [] left 0 n len(s) while left n: right left while right n and s[right] s[left]: right 1 length right - left if length 3: compressed.append(f{s[left]}{length}) else: compressed.append(s[left:right]) left right result_str .join(compressed) # Step 3统计排序 cnt {} for ch in result_str: cnt[ch] cnt.get(ch, 0) 1 items sorted(cnt.items(), keylambda x: (-x[1], x[0])) return .join(f{ch}{num} for ch, num in items) if __name__ __main__: line sys.stdin.readline().strip() print(compress_and_count(line))2.3 复杂度分析与必须注意的边界情况这个解法的时间复杂度是O(n log n)瓶颈在排序空间复杂度O(n)。对于长度在10^5级别的字符串完全够用。边界情况我列一个清单每一条都是真实机试中会被卡住的点字符串为空直接返回空串程序不能崩。整个字符串就是连续同一字符比如aaaa压缩结果是a4然后统计只有一个a出现一次。注意这里数字4是作为拼接信息不是参与统计的字符不能把4也统计进去。片段长度为3和长度为2的处理不同长度正好3也要压缩长度2不压缩两种情况相邻出现时要能正确处理。数字和字母混排比如111aaa压缩后是13a3。很多同学会写错压缩顺序将1和3当成数字1和3导致统计出字符1两次、3一次这是错的。我当初第一次写这题就是在“数字作为压缩信息”和“数字作为统计对象”之间搞混了。记住一条原则压缩产生的数字只用于显示不进入统计源。所以先压缩完得到一个字符串再拿这个字符串做统计顺序不能反过来更不能在原串上边压缩边统计。2.4 一道送分题的提分技巧这类所谓“送分题”恰恰是最容易拉开分差的。90%的人能写出一个能跑的版本但只有30%的人能一次ACAccepted通过全部测试。我的经验是写完后不要急着提交手动跑三个自定义用例——空字符串、全相同字符、无任何连续字符。这三个用例涵盖了绝大多数边界逻辑能帮你拦截掉80%的WA。另外输出格式上留意是否需要换行机试里print默认带换行没问题但如果你用sys.stdout.write记得自己补\n。3. 第二题分水岭题跳跃游戏变体与贪心策略3.1 题目原型与难点拆解第二题通常会从“跳跃游戏”或者“最少区间覆盖”这类经典问题变形而来。模拟题5里第二题的原型是这样的给定一个非负整数数组 nums你初始位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。假设现在额外给出了一个限制你必须恰好使用 k 次跳跃到达数组末尾问是否存在这样的跳跃方案如果存在输出每次跳跃的距离否则输出 -1。这题直接把原先的“最少跳跃次数”改成了“恰好k次跳跃是否存在方案”难度瞬间上升了一截。难点不在于算法本身而在于“恰好k次”意味着不是贪心地每次跳最远就完事了中间可能存在“多跳几步”或“缩短某次跳跃”来凑次数的情况。输出“每次跳跃的距离”意味着代码里要记录路径单纯返回能否到达是不够的。3.2 为什么不能用“纯贪心”而要用“贪心倒推”的组合思路普通跳跃游戏直接贪心维护max_reach就能过。但“恰好k次”这个约束让直接贪心失效了因为贪心只保证“跳到最远”不保证“次数刚好”。我采用的方案是先做一次可行性判断再用倒推法构造路径。可行性判断如果数组长度n那么最少需要的跳跃次数是min_jumps最多能使用的跳跃次数是n-1每次都跳一步。所以只有min_jumps k n-1时才存在方案。构造路径从终点开始往前数先确定“最后一次跳跃”的起点这个起点必须满足nums[prev] n-1 - prev并且要让剩余的跳跃次数k-1还能在“起点之前”完成。这个倒推过程保证了每次选择都有回旋余地。3.3 完整代码实战def jump_game_with_k(nums, k): n len(nums) if n 0: return -1 if n 1: return [0] if k 0 else -1 # 1. 计算最小跳跃次数经典贪心 min_jumps 0 cur_end 0 cur_far 0 for i in range(n - 1): cur_far max(cur_far, i nums[i]) if i cur_end: min_jumps 1 cur_end cur_far if cur_end n - 1: break if min_jumps k or k n - 1: return -1 # 2. 倒推构造恰好k次跳跃的路径 # jumps数组存放每次跳跃的距离从后往前填 jumps [0] * k pos n - 1 remaining k for step in range(k, 0, -1): # 要找前一个位置pre要求 # 1) pre pos # 2) nums[pre] pos - pre # 3) 从起点到pre至少需要 step-1 次即 pre step-1保证剩余次数够用 chosen -1 for pre in range(pos - 1, step - 2, -1): if nums[pre] pos - pre: chosen pre # 为了给前面的跳跃留足空间选尽可能靠左的合法位置 # 所以这里不break继续向左找 if chosen -1: return -1 jumps[step - 1] pos - chosen pos chosen remaining - 1 if pos ! 0: return -1 return jumps if __name__ __main__: # 样例nums [2, 3, 1, 1, 4], k 2 nums list(map(int, input().split())) k int(input()) res jump_game_with_k(nums, k) if res -1: print(-1) else: print( .join(map(str, res)))3.4 为什么倒推时要“选尽可能靠左的合法位置”这里有个很容易被忽略的细节我当年就栽过。假设我们从终点倒推存在多个满足nums[pre] pos - pre的前驱位置pre那应该选哪一个如果选靠右的pre那么“剩余前面的路”就更长需要的跳跃次数也就更多而我们的目标恰恰是“恰好k次”如果前段可用次数不够方案就失效了。选尽可能靠左的合法位置相当于把“步数需求”往前转移给前面预留更多空间这样更容易凑出k-1次。这和“正着贪心选最远”是镜像关系。这种倒推思路本质上是一种贪心构造法它依赖一个关键前提只要可行性条件满足那么“尽量靠左”的选法一定不会破坏解的存在性。严格证明可以用归纳法但实操时你只需要记住这个结论就行。3.5 这类题的复杂度陷阱这个解法最坏情况下内层寻找pre的循环是O(n)外层是O(k)所以整体是O(n*k)。当k接近n时就是O(n^2)在n10^5时会超时。如果担心超时可以把“找前驱”改成维护一个单调数据结构但机试中大部分用例的n在10^4以内O(n*k)能过。我不建议你在考场上追求最优解先把能AC的方案写出来再去优化。很多同学就是纠结于O(n log n)的极致解法结果时间不够第二题直接空白这才是最大的浪费。4. 第三题压轴题依赖调度与拓扑排序实战4.1 题目原型与建模关键第三题通常是一个带依赖关系的任务调度问题模拟题5里它长这样有 n 个任务编号从 0 到 n-1。给定 m 条依赖关系 (a, b)表示任务 a 必须在任务 b 之前完成。现在假设每个任务执行都需要 1 个单位时间所有任务可以用无限个处理器并行执行。要求输出最早完成所有任务所需的时间并输出一个可行的执行顺序如果依赖关系存在环输出 -1。这个题目是典型的拓扑排序问题但它比教材上的基础拓扑排序多了一层“最少时间”和“可行顺序”都需要输出。我在实际教学中发现初学者最容易卡的地方不是拓扑排序本身而是不知道如何把“并行执行”转化成算法逻辑。4.2 从“并行执行”到“分层拓扑排序”如果所有任务可以并行执行最早完成时间其实取决于“最长依赖链的长度”。比如A→B→C这条链即使D不依赖任何人也得等C完成后整个流程才算结束所以总耗时是链长而不是任务总数。要计算这个时间最直观的方式是对拓扑排序做分层处理每一轮把所有入度为0的任务同时取出作为同一层层数就是最终耗时。每一层之间的任务不存在依赖关系可以并行因此层数即最短时间。同时记录每一层取出的任务就得到了一个满足拓扑顺序的执行序列。这个序列不一定唯一但一定合法。4.3 代码实现与细节from collections import deque def schedule_tasks(n, edges): indeg [0] * n graph [[] for _ in range(n)] for a, b in edges: graph[a].append(b) indeg[b] 1 # 初始化入度为0的节点 q deque([i for i in range(n) if indeg[i] 0]) order [] time 0 while q: # 当前层的节点数 size len(q) for _ in range(size): cur q.popleft() order.append(cur) for nxt in graph[cur]: indeg[nxt] - 1 if indeg[nxt] 0: q.append(nxt) time 1 # 如果order长度不等于n说明有环 if len(order) ! n: return -1, [] return time, order if __name__ __main__: n int(input()) m int(input()) edges [] for _ in range(m): a, b map(int, input().split()) edges.append((a, b)) t, seq schedule_tasks(n, edges) if t -1: print(-1) else: print(t) print( .join(map(str, seq)))4.4 环检测与原理解读环检测的原理非常好记拓扑排序每次删掉的都是“当前不依赖任何人”的任务。如果存在环环上的每个节点永远都有一个前置任务没被删除入度永远不会降到0所以最后order的数量一定小于n。有一个经典的比喻你早上起床穿衣服袜子、裤子、鞋之间是有依赖顺序的但如果某天你把“穿左鞋”和“穿右鞋”定义成互相依赖左鞋必须先穿右鞋右鞋必须先穿左鞋那这个序列就永远排不出来。拓扑排序就是帮你发现这种“死锁”的算法。在华为机试中环检测的输出非常严格必须是-1不能附带别的信息。如果你把-1换行后再输出其他内容会被判格式错误。我见过的很多同学是算法对了最后多打了一个空格或换行被扣分。4.5 第三题的进阶思考如果执行时间各不相同怎么办考场上有余力的朋友可以顺手想一下这个变体如果每个任务的执行时间不再固定为1而是cost[i]那么“最早完成时间”就不再是简单分层数而要对每个节点计算max(前置节点完成时间) cost[i]最终答案是所有节点完成时间的最大值。这个模型在实际项目排期里非常常见算法原理其实是在拓扑序上做动态规划。如果模拟题5里第三题你没有思路先把基础拓扑排序写对这个变体能说出思路也是加分项。毕竟机试只要求AC但面试官问起来的时候你能展示出这种“举一反三”的能力会很有说服力。5. 机试实战避坑清单与刷题建议5.1 我见过的五个典型“翻车点”先把我总结的考场翻车点摆在这你刷题时对照着自查不读完整题目说明。机试的题面很长包含样例解释和边界限制。很多人只看输入输出样例就开始写结果漏掉“压缩只处理连续3次以上”这种关键规则白白丢掉一半分数。输入解析写死。华为机试有时代理环境会多出空行或者在数字之间夹杂多余空格。稳妥做法是split()而不是手动按固定位置切片尤其是处理不定长的数组输入时。Python版本差异。机试系统有时候是PyPy有时候是CPython个别库函数行为有差异。我的习惯是避免依赖冷门库和Python 3.10的新特性尽量用3.8版本通用的写法。不处理样例之外的大数据。自己测试时只跑题目给的样例很容易忽略极端情况。时间允许的话自己构造一个n10^5的随机数据跑一遍确认不超时。临场心态崩了。第三题写不出来很正常不要死磕。先把前两题分数拿满再回来啃第三题。很多拿Offer的人第三题也只过了一半测试点这不影响综合评分。5.2 考前一周的模拟训练建议如果你还有一周就要机试我不建议你再盲目刷新题而是做三件事第一严格按照考试时间做三次完整模拟。定好闹钟两个半小时三题一气呵成。模拟的时候不用管分数重点关注“时间分配”“输入输出处理”“边界调试”这三次迭代的流畅度。第二把做过的题分门别类整理成模板。字符串处理类一个模板、BFS/DFS一个模板、拓扑排序一个模板、动态规划一个模板。考试的时候不是靠临场推导而是靠“识别题目类型→套模板→调细节”这个流程。第三背熟你自己的代码模板而不是背答案。考场压力下你能流畅写出来的只有那些肌肉记忆已经印在脑子里的代码。所以最后几天多敲几遍自己整理过的模板比追新题有用得多。5.3 我的个人体会机试这关拼的从来不只是“聪明”更多是“熟练”和“稳”。我见过数学系大佬因为输出格式错被扣到崩溃也见过非科班同学用最朴素的BFS三题全过。复盘下来拉开差距的就是那几样东西对输入输出的敏感度、对边界条件的肌肉记忆、以及遇到卡壳时快速换思路的能力。这套“华为机试编程模拟题5”覆盖了字符串、双指针、贪心构造、拓扑排序、环检测等机试高频考点你把每一题的“为什么这么做”吃透再自己独立重写一遍收获会比闷头刷二十道重复题大得多。希望这篇拆解能成为你冲刺路上的一块垫脚石。