1. 华为机试到底在考什么先把规则吃透如果你正在准备华为OD机试或者投了华为软件开发岗之后收到了机试通知那你一定绕不开在线编程这道门槛。我最近把一套“华为机试编程模拟题8”从头到尾刷了两遍一个很直观的感受是这套题不偏不怪难度梯度也接近真实考试但特别能暴露基本功。今天这篇就把我对这套模拟题的拆解过程、每道题的完整解法、以及考场上容易被扣分的细节全部写出来给准备机试的朋友一个可以直接照着练的参考。先说机试的整体规则因为很多人第一步就栽在信息差上。华为机试通常是3道编程题我遇到的批次是100分、200分、300分的分数梯度三题总分600通过分数线看具体部门和招聘类型。题目类型高度集中在字符串处理、数组和排序、双指针、动态规划、图论、贪心这几类。第一题基本是送分题考简单逻辑和字符串操作第二题开始上难度一般是中等复杂度的数据结构或贪心问题第三题就是真正拉开差距的题经常涉及动态规划或图论需要你能快速把实际问题抽象成模型。模拟题8这套卷子在所有模拟卷里算是不错的自测材料。它没有拿极偏的算法来刁难你三道题分别覆盖了字符串、区间合并、依赖关系调度恰好对应了机试中最常出现的三个方向。我建议刷题顺序不要打乱先把100分的题快速拿下确保不丢分200分的题留15到20分钟300分的题至少留30分钟。如果你是第一次接触华为机试强烈建议先找一套模拟题完整测一次先感受一下时间压力和平台环境再进入专题训练。1.1 三道题的分值与难度分布机试不是ACM不会要求你写非常复杂的板子但也不会像校内考试那样放水。100分的题通常只考单一知识点比如字符串遍历、简单模拟、哈希表统计代码量一般不超过30行。这种题必须一遍过因为后面的大题很吃时间。200分的题会开始考思维常见的有滑动窗口、合并区间、拓扑排序、背包问题变种。这类题的特点是你知道用什么算法但实现细节容易出错尤其是边界条件。很多人在200分题上卡住等调通了时间已经不够做第三题了。所以平时练习时要有意识地给自己定时间不能一直磨。300分的题一般是“算法模板 实际问题包装”的组合。比如给你一个任务依赖关系让你算最短完成时间表面上是工程调度本质上就是求DAG上的最长路径。只要能把外壳剥掉看到里面的图论模型代码写起来并不难。难的是你能不能稳定地完成这个抽象过程。模拟题8的第三题就是很好的练习样本后面我会详细拆。1.2 模拟题8在整个刷题路线里的位置如果你是从零开始备考我的建议是不要一上来就刷模拟题而是先按专题过一遍基础算法字符串、排序、二分、双指针、DFS/BFS、动态规划入门、最短路径。这个过程大概需要一到两周每天保持3到5道题的节奏。之后再做模拟题模拟题8适合放在这个阶段的中后段。它的作用是帮你确认自己是不是真的掌握了基础而不是自我感觉良好地刷完了几百道题。我见过很多准备了两周的人剑指offer刷了不少但一上机试还是慌原因就是平时练习没有时间限制也没有环境干扰。模拟题8在这种情况下就是照妖镜它能直接暴露你的读题速度、编码速度和查错能力。2. 模拟题8典型题目拆解从读题到AC下面我把模拟题8里最有代表性的三道题做了一次同型改写题目本身不涉及真实题库内容但题型、难度和考点基本是等价的。每道题我都会按“题面、输入输出、思路、代码、复杂度”的顺序来讲方便你直接照着练。2.1 第一题字符串压缩简单题这一题对应机试里的100分题。题面可以描述为给定一个仅由小写字母组成的字符串长度不超过10000要求把连续相同的字符压缩成“字符出现次数”的形式比如aabcccccaaa压缩后是a2b1c5a3。但如果压缩后的字符串长度不小于原串长度则输出原串。这道题一眼就能看出是字符串遍历加计数代码量很小。但有两个细节容易被忽略。第一空字符串的处理虽然机试一般不会给空串但写防御性代码总没错。第二末尾那组连续字符也要补上很多人在循环结束后忘记处理最后一组导致输出少一段。def compress(s: str) - str: if not s: return s res [] cnt 1 for i in range(1, len(s)): if s[i] s[i - 1]: cnt 1 else: res.append(s[i - 1] str(cnt)) cnt 1 res.append(s[-1] str(cnt)) compressed .join(res) return compressed if len(compressed) len(s) else s print(compress(input().strip()))这里用列表收集拼接片段而不是直接做字符串累加是一个好习惯。虽然长度10000对字符串拼接性能影响不大但如果以后遇到更长字符串在循环里可能产生大量临时对象。机试里不追求极致的微优化但写代码时顺手用列表推导和join()能减少很多无谓的性能损耗。复杂度是O(n)只需要一次遍历。这类简单题在机试里的坑反而是“想太多”。比如有人会去考虑用哈希表统计每个字符总次数结果把顺序信息丢了。这题强调连续相同不是全局统计认真读题比急着写代码更重要。2.2 第二题区间合并中档题第二题我遇到的是区间合并输入N个区间每个区间用[l, r]表示一段连续占用时间需要把所有有重叠的区间合并最后输出合并后区间的个数以及合并后最长的区间长度。这道题的核心思想很经典第一步按左端点排序第二步遍历区间并维护当前合并的右边界。判断两个区间是否重叠看当前区间的左端点是否小于等于已合并区间的右端点。如果重叠就更新右边界为两者最大值如果不重叠就把当前合并区间收尾开始新的合并。n int(input()) intervals [] for _ in range(n): l, r map(int, input().split()) intervals.append((l, r)) intervals.sort(keylambda x: x[0]) merged [] for l, r in intervals: if not merged or l merged[-1][1]: merged.append([l, r]) else: merged[-1][1] max(merged[-1][1], r) print(len(merged)) print(max(r - l for l, r in merged))这段代码里有一个容易被忽略的细节题面说的是“有重叠”不包括相邻区间。所以判断条件用l merged[-1][1]而不是l merged[-1][1] 1。有些题目会把“相邻也合并”写进去这时候要改成l merged[-1][1] 1。这个区别就是审题问题我见过不少人在这种地方丢分。另外max(r - l for l, r in merged)这一步如果merged为空会报错。虽然输入保证N至少为1但如果你为了程序健壮性可以加一个判空条件。复杂度方面排序是O(n log n)合并是O(n)这题只要能想到排序基本就解决了一半。考场上很多人会卡在“如何求最长区间”上其实合并完直接遍历一次就行完全不需要额外维护什么复杂结构。区间类题目的通法就是“排序加扫描”你把这个套路吃透类似题目都能应付。2.3 第三题项目依赖与最短完成时间难题这题是整套模拟题的压轴题。题面可以描述为一个项目里有N个任务编号从1到N每个任务有一个固定的耗时。任务之间存在M条依赖关系每条关系用u v表示“任务u必须在任务v开始之前完成”。假设资源充足任意多个任务可以并行执行现在要计算整个项目的最短完成时间输入保证依赖关系无环。这个题的本质是求有向无环图上的最长路径也叫关键路径。为什么是最长路径而不是最短路径因为任务之间是并行关系所有依赖链同时开始整个项目的完成时间取决于最长的那条依赖链。比如任务A要3天任务B要2天且B依赖A那么从开始到B结束至少要5天如果还有个独立任务C要10天那总时间就是10天和5天中较大的那个因为C可以和A、B并行。实现上我用邻接表存图先统计每个节点的入度再把入度为0的节点加入队列。用dp数组记录到当前任务为止的最长累计耗时。初始时dp[i]等于任务i自身的耗时。当从队列中取出节点u遍历它的所有后继节点v时尝试用dp[u] cost[v]更新dp[v]同时将v的入度减1减到0就把v入队。from collections import deque n, m map(int, input().split()) cost [0] list(map(int, input().split())) indeg [0] * (n 1) graph [[] for _ in range(n 1)] for _ in range(m): u, v map(int, input().split()) graph[u].append(v) indeg[v] 1 dp [0] * (n 1) q deque() for i in range(1, n 1): dp[i] cost[i] if indeg[i] 0: q.append(i) while q: u q.popleft() for v in graph[u]: dp[v] max(dp[v], dp[u] cost[v]) indeg[v] - 1 if indeg[v] 0: q.append(v) print(max(dp[1:]))这段代码有两个关键点。第一个是dp的初始化很多人在拓扑排序里忘了先把每个节点的自身耗时填进去导致结果偏小。第二个是更新时机必须在“访问出边”时更新后继节点而不是等节点出队时才更新自身否则会丢掉前面累积的信息。如果图里有多个终点最终答案要取所有dp值里的最大值。如果M特别大注意用邻接表而不是邻接矩阵否则光存图就可能超内存。这题的时间复杂度是O(NM)已经是当下的最优解。我刷这题时第一遍写成了DFS找所有路径结果在分支较多时重复计算直接超时。后来换成拓扑排序加DP思路一下清晰了。所以遇到有依赖关系的调度问题第一反应应该是拓扑排序而不是暴力搜索。3. 机试实战中的代码规范与输入输出细节很多练习时能写出正确代码的人一到机试平台就各种报错问题往往不在算法本身而是栽在输入输出和代码规范上。华为机试用的是在线评测系统对输出的要求很严格多一个空格、少一个换行都可能导致Wrong Answer。3.1 输入读取的几种方式别在IO上翻车Python选手最常犯的错误是用input()时没处理字符串末尾的换行或者读到空行时直接崩溃。如果你不确定当前行是否有内容可以用sys.stdin.read()一次性读取所有内容然后按空白字符分割。这样不管输入换行还是空格分隔都能统一处理。缺点是如果题目要求保持行顺序你得先读下一行再分割。一个比较通用的做法是import sys data sys.stdin.read().split() it iter(data) n int(next(it)) m int(next(it))这种写法在输入规模较大时比反复调用input()更快也不容易出现边界问题。但是要注意如果题目要求读取的字符串可能包含空格就不能用split()直接拆需要结合strip()和指定的分隔符处理。在读整数列表时list(map(int, input().split()))是常规操作但如果某一行可能为空比如输入末尾多了一个空行input().split()会返回空列表map转换后列表为空后面访问下标就会报错。所以读取前最好判断一下。3.2 复杂度估算200ms之内你的代码能跑多少量级机试平台的时间限制通常用毫秒表示C大概1到2秒Python虽然有时会放宽但也不能肆无忌惮地写O(n^2)。你需要建立一个粗略的估算体系在普通OJ上Python每秒大约能执行10^7到10^8次简单操作。所以当n10^5时O(n^2)意味着10^10次操作绝对超时但如果n1000O(n^2)就没问题。我在做模拟题8第三题时一开始用DFS穷举所有路径遇到分支多的情况就是指数复杂度数据一大直接超时。后来改成拓扑排序O(NM)就轻松过了。所以动手前先看一眼数据范围这能帮你快速排除错误方向。比如看到n最大是10^5就不要犹豫立刻放弃任何依赖多重循环的方案。还有个细节Python的递归深度默认只有1000如果题目要求DFS遍历一个上万节点的图直接递归会报RecursionError。要么用sys.setrecursionlimit(1000000)要么改成栈或队列的迭代写法。机试平台上这个坑特别常见。3.3 用例自测把边界值写进测试很多人写代码只测题目给的示例跑通了就提交结果惨遭“通过率0%”。机试判卷不仅有示例用例还有大量隐藏边界用例。你需要养成自测习惯至少覆盖这几类空输入、单元素输入、所有元素相同、所有元素不同、最大数值、最小数值、乱序输入。比如字符串压缩那题测试abcd应该输出原串因为压缩后更长。测试aaaa应该输出a4。区间合并那题测试区间完全不重叠、完全包含、一个区间覆盖多个区间等情况。依赖调度那题测试没有依赖关系、只有一个任务、存在多条独立路径的情况。你可以在本地写一个简单的暴力解法然后用随机小数据对比这就是“对拍”。机试时虽然不能引用外部工具但你可以自己生成小规模用例用数学逻辑验证答案无误。平时练习养成了对拍习惯考场上即使没有脚本也能在脑内快速演算。4. 常见问题与掉分点实录这里我把实战中遇到的高频问题整理成一份速查表都是真实踩过的坑比任何理论都实用。现象可能原因解决办法样例通过提交后0分没有处理多组输入或输出格式多打了空格用sys.stdin.read统一读取输出前检查每个字符代码本地正常平台报超时算法复杂度爆炸或递归过深换思路用迭代而非递归减少无意义遍历部分用例数组越界下标从1开始但遍历范围写成0到n统一约定任务编号是1还是0开头写注释输出结果比预期大很多dp初始化漏了节点自身耗时检查所有入度为0的节点初始值是否等于cost合并区间结果多了或少了判断重叠的条件写错或者没有先排序先sort by左端点再用当前r与下一个l比较用input()读整数遇到空行崩溃输入末尾有空白行用try except EOFError或sys.stdin.read第三题DFS爆栈递归深度超过Python默认限制拓扑排序 DP替代DFS路径枚举除了这些还有一个是心态问题。机试时间很紧很多人在第一题上反复纠结输出格式结果浪费了20分钟。实际上第一题分值最低完全不应该花那么多时间。我的建议是先快速浏览三道题花1到2分钟判断难度然后从第一题开始做如果5分钟内没有思路跳到第二题最后再回头处理。第三题如果完全不会也要写一个暴力版本拿部分分。很多评测系统是按测试点给分的暴力解法能过掉一部分小数据比空着交白卷强太多。见过太多人因为第三题看了5分钟没思路就直接退出其实哪怕只写一个最简单的DFS也能拿不少分。在排查超时问题时还有一个技巧先看数据范围再决定优化策略。如果n只有1000O(n^2)没问题如果n是10^5就要用二分、双指针、哈希表或者排序。不是所有题目都需要最优解够用就行把时间留给后面的题更重要。5. 备考节奏与个人心得刷了这么多套模拟题我最大的心得是华为机试考的不是你会不会某个难题而是你在有限时间内能不能稳定地把会做的题全部做对。所以备考要分阶段不能一直沉浸在做新题的快感里。5.1 三轮刷题法第一轮按专题刷把字符串、排序、双指针、DFS/BFS、动态规划、图论这些高频考点逐个击破。每做完一类题总结一个自己习惯的模板。比如DFS可以写成函数内递归DAG最长路径可以用拓扑排序加DP。模板不用多但要足够熟练考场上能直接默写。第二轮开始成套刷模拟题一天一套或两天一套严格按照机试的时间要求来。这一轮的目标是提升“读题 → 抽象 → 写码 → 调试”的整体速度。模拟题8就适合放在这个阶段因为它难度中等偏上能有效暴露你的薄弱环节。做完后一定要复盘把每道题用了多长时间、卡在哪里、为什么卡都记录下来。第三轮是冲刺阶段不需要再做很多新题把之前错过的题重新刷一遍整理一份“易错点清单”。我在考前做的最后一件事情就是把所有容易忽略的边界条件抄在一张纸上比如空输入、单元素、最大值、下标从1开始等。考场上犯迷糊的时候看一眼比临时回忆强得多。5.2 机试当天要注意的事机试当天设备的网络环境是关键。华为OD机试现在很多采用双机位监控电脑摄像头作为第一机位手机扫码作为第二机位。开考前一定要提前测试摄像头和麦克风手机要充满电并确保答题过程中不会因为设备问题被中断。我见过一个人因为手机锁屏导致第二机位掉线直接取消了当次成绩这太可惜了。开始答题后先把所有题都看一遍标记每道题的大致难度和你想到的算法方向。然后按顺序做但不要在一道题上死磕超过30分钟。如果代码写了一半发现思路不通果断放弃换题不要觉得“都写了一半舍不得”。机试是按通过测试点给分的半成品代码可能一分都没有。最后再分享一个小细节输出的时候不要画蛇添足。题目要求输出一个整数你就只输出一个整数不要加“结果是”这类前缀。评测系统只认标准输出任何多余字符都会判错。平时练习就可以养成习惯输出前先确认“这行输出是不是题目要求的格式”。我个人刷完模拟题8之后最大的变化是看到“依赖任务”这类题不再害怕了。它表面上是工程调度其实就是图论模板加一点动态规划思想。你能不能在考场上快速想到这个模型取决于平时刷题时有没有刻意训练抽象能力。如果时间有限优先把字符串处理、排序、动态规划和最短路这些高频考点练熟机试通过率会有明显提升。