你们有没有那种感觉刷题刷到第8套模拟题的时候突然意识到前面7套都白刷了。我第一次做华为机试编程模拟题8的时候愣是看着一道字符串题发了十分钟呆。倒不是题目有多难而是它把很多平时刷题时忽略的细节全揉在一起比如输入格式的坑、边界条件的判定、还有那些稍微一变型就认不出来的老题目。这篇文章我就拿模拟题8当引子把华为机试备考里最值得花时间的几个地方完整拆一遍包括题型结构、高频算法考点、具体代码实现、输入输出陷阱还有我踩过的那些坑。我知道关注华为机试的人不少是准备OD机试的也有的是为了校招、保研机试或者单纯想练手。不管你是哪一种模拟题的价值都不在于“背答案”而在于帮你摸清楚出题人的套路。模拟题8这套卷子我前前后后做了三遍每一遍都有新发现。下面我按自己的复盘顺序来讲不整虚的全是实操。1. 模拟题8这套卷子到底在考什么1.1 华为机试的难度定位与考察范围华为机试的难度说高不算高说低也绝对不低。它卡在“校招笔试”和“面试手撕代码”中间比LeetCode的Medium略简单但对时间把控的要求非常高。大部分人不是不会做而是第一题花太多时间导致后面简单题没时间写。考察范围基本固定在四块字符串处理、线性表数组、链表、栈、队列、动态规划、简单图论。很少出现特别偏的算法什么后缀数组、网络流、计算几何基本不会考。但这不代表你可以不准备因为每道题都会在基础题上套一层业务场景比如“日志解析”“资源分配”“任务调度”本质是算法题但披了一层壳。模拟题8尤其明显三题分别对应了字符串模拟、动态规划、图论拓扑难度梯度也拉得比较开第一题送分第二题要仔细第三题是拉分题。我第一次做这套卷子第一题用了二十分钟第二题写了半天没全对第三题只过了样例最后总分惨不忍睹。但恰恰是这种“被虐”的感觉让我后面真正上考场的时候稳了很多。1.2 题型结构与分值分布华为OD机试一般情况下是三道题总分400分常见分值是第一题100分、第二题100分、第三题200分整体通过要求通常看总分是否达标。模拟题8也是按这个结构设计的。第一题是纯字符串处理属于“你只要读懂题就能做”的类型用来保底。第二题是动态规划需要你自己从描述里抽象出状态模型属于区分选手的分水岭。第三题是任务调度相关考察拓扑排序和图建模能力难度比前面高一个档次它的用例比较多光靠暴力往往过不全。有几点要注意华为机试的算分逻辑不是按测试点比例给分的而是按照“通过率”和“边界处理”来评定。也就是说你写了一堆代码但只过了最简单的一个例子很可能拿不到多少分。反过来如果你能把边界情况全考虑进去哪怕算法不是最优解也能拿不错的分。这个特性在后文会反复出现。1.3 和真实OD机试C卷的对比现在大家讨论比较多的是OD机试新系统、双机位监考和C卷。新系统意味着考试环境更规范双机位则一定要提前调试好设备别等到考试当天才发现摄像头不对。至于C卷的题目风格我练完模拟题8再对比网上流传的真题题库目录发现模拟题8的命题思路和C卷高度一致题干长、场景杂、边界多。比如它会给你一段日志里面有几条记录每条记录的字段有缺失让你判断哪些合法或者给你一个依赖关系表让你计算某个任务能不能执行。这种题目在牛客网和LeetCode上很难找到完全一致的只有靠平时积累“读题抽象”的能力。所以如果你时间有限与其刷几百道LeetCode不如集中刷几套仿真模拟题把每一道题的出题套路吃透。模拟题8就是我用来“摸底”的最佳工具。2. 先把高频算法考点的底层逻辑弄清楚2.1 字符串处理与正则表达式的边界华为机试十道题里至少有四道和字符串有关字符串处理的核心不是背API而是理解“边界”。拿模拟题8的第一题举例题目是字符串解压格式类似3[ab]2[c]要输出abababcc。这种题看着简单但面试和机试里最容易丢分的就是括号嵌套、数字重复次数为0、空字符串这些情况。在Python里很多人第一反应是用正则re.findall去提取数字和括号但正则写起来要考虑嵌套关系反而不如手写栈来得稳。我会在第三部分给出完整的栈解法这里先强调一个原则任何字符串处理题都要先想清楚“特殊输入”是什么比如空串、单个字符、嵌套多层、数字后有空格等。把边界全列出来再动手写代码。2.2 栈和队列在括号匹配、单调栈中的应用栈是机试里性价比最高的数据结构。它不仅能做括号匹配还能做表达式求值、最小栈、单调栈等。模拟题8里的字符串解压本质就是一个栈问题遇到数字就记录重复次数遇到[就把当前字符串压栈遇到]就出栈并重复拼接。我经常用一个生活类比来解释栈就像一摞盘子你只能从最上面拿起或放下。字符串嵌套时越晚出现的左括号越早被闭合这天然符合栈的后进先出特性。所以一旦看到“嵌套”“闭合”“回溯依赖”这些词优先想到栈。单调栈在华为机试里也出现过典型题目是“柱状图中最大的矩形”和“每日温度”。这类题的难点不是栈本身而是你得能想到用单调栈来把 O(n²) 优化成 O(n)。如果平时没练过考场上是很难临场推导出来的。所以模拟题8之外建议再单独练十几道单调栈题形成肌肉记忆。2.3 动态规划的核心状态定义与转移方程动态规划是华为机试的第二题常客也是大多数人最头疼的部分。我见过很多人的问题是代码写了上百行但状态定义一开始就错了后面全都白搭。学动态规划最重要的不是背模板而是掌握两个动作定义状态、写转移方程。比如模拟题8的第二题求连续子数组的最大乘积。这个题和最大子段和很像但难点在于负数两个负数相乘可能变成正数所以不能只维护一个最大值得同时维护当前位置能取到的最大值和最小值。状态定义是dp_max[i]表示以第 i 个元素结尾的子数组的最大乘积dp_min[i]表示以第 i 个元素结尾的子数组的最小乘积。转移时当前元素 nums[i] 可能单独成段也可能和前面的段拼接所以dp_max[i] max(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])dp_min[i] min(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])这个转移方程为什么这么写因为乘积的符号会变最大值可能来自“之前的最大值 × 当前正数”也可能来自“之前的最小值 × 当前负数”。把这个想通了动态规划就没有那么神秘。2.4 图论与拓扑排序的题目识别模拟题8的第三题是任务调度这类题在华为机试里出现频率不低因为华为很多产品场景本身就涉及任务编排、依赖关系、资源调度。识别图论题的方法很简单题干里出现“依赖”“先后顺序”“不能同时执行”“循环引用”等关键词就要往有向图方向想如果题目要求判断是否有环、能否完成所有任务那就要上拓扑排序。拓扑排序的Kahn算法核心就是用入度数组和队列。先把所有入度为0的节点入队然后逐个出队把出队节点指向的节点的入度减1减到0就继续入队。如果最后出队节点数不等于总节点数说明图里有环。这个算法的空间复杂度是 O(VE)时间复杂度也是 O(VE)在机试的输入规模下完全够用。重点要注意的是节点编号可能不是从0开始而是从1开始或者带字母处理的时候要建好映射关系。3. 模拟题8重点题目的完整解题思路与代码实现3.1 第一题字符串解压题目描述大致是给定一个压缩后的字符串形如3[ab]2[c]数字表示方括号内字符串重复的次数支持嵌套例如2[a3[b]]解压后是abbbabbb。输出解压后的完整字符串。我自己的实现思路是用两个栈一个存字符串一个存数字遍历字符串遇到数字时把完整数字拼接出来因为可能是多位比如12[a]。遇到字母时拼到当前字符串上。遇到[时把当前字符串和数字分别压入栈然后重置。遇到]时弹出数字和之前的字符串把当前字符串重复数字次然后拼到之前的字符串后面。代码用Python写出来非常直观def decode_string(s: str) - str: num_stack [] str_stack [] cur_str i 0 n len(s) while i n: ch s[i] if ch.isdigit(): num 0 while i n and s[i].isdigit(): num num * 10 int(s[i]) i 1 num_stack.append(num) continue elif ch [: str_stack.append(cur_str) cur_str elif ch ]: repeat_times num_stack.pop() prev_str str_stack.pop() cur_str prev_str cur_str * repeat_times else: cur_str ch i 1 return cur_str这段代码有两个细节值得说。第一是数字处理很多人直接用int(ch)导致多位数字出错第二是cur_str prev_str cur_str * repeat_times这个顺序一定不能写成cur_str * repeat_times prev_str否则嵌套的拼接顺序就反了。我第一遍做就栽在这个顺序上样例怎么调都不对。这类题的复杂度是 O(S)S 是解压后的字符串长度。如果嵌套特别深递归写法可能栈溢出所以用显式栈更稳。机试环境一般不限制递归深度但判断不严还是建议养成用栈的习惯。3.2 第二题连续子数组的最大乘积题目描述给定一个整数数组求所有连续子数组中乘积最大的值。数组长度最大可能就是十万级别所以 O(n²) 暴力是肯定过不了的。我在2.3节已经讲了动态规划的状态定义这里直接给完整实现def max_product(nums): if not nums: return 0 dp_max nums[0] dp_min nums[0] result nums[0] for i in range(1, len(nums)): if nums[i] 0: dp_max, dp_min dp_min, dp_max dp_max max(nums[i], dp_max * nums[i]) dp_min min(nums[i], dp_min * nums[i]) result max(result, dp_max) return result这里用了一个小技巧当nums[i]为负数时交换dp_max和dp_min。因为乘以负数会翻转大小关系交换之后dp_max * nums[i]就变成了原来的“最小值在当前负数下能达到的最大值”逻辑更简洁也避免了写三参数 max 带来的混乱。这种写法在LeetCode上也算标准解但放到华为机试里要注意输入可能包含0。有0的时候乘积会归零此时dp_max可能变成0但这不会影响最终结果因为后面正数还能重新开始。如果你实现的是“必须连续”的版本一定要把0单独作为候选值考虑进去。3.3 第三题任务调度与依赖关系题目描述有 n 个任务编号从 0 到 n-1给定若干依赖关系[a, b]表示任务 b 依赖任务 a也就是要先完成 a 才能完成 b。请判断是否可能存在一种执行顺序让所有任务都能完成如果可以输出任意一种顺序。这不就是拓扑排序的裸题吗Kahn算法直接上from collections import deque def can_finish(num_tasks, prerequisites): graph [[] for _ in range(num_tasks)] indegree [0] * num_tasks for a, b in prerequisites: graph[a].append(b) indegree[b] 1 q deque() for i in range(num_tasks): if indegree[i] 0: q.append(i) order [] while q: node q.popleft() order.append(node) for neighbor in graph[node]: indegree[neighbor] - 1 if indegree[neighbor] 0: q.append(neighbor) if len(order) ! num_tasks: return [] # 存在环无法完成 return order这段代码最容易被忽略的地方是num_tasks和实际出现的节点编号可能不一致。有些题目输入里依赖关系只包含部分任务还有一些任务没出现在依赖关系中此时它们入度为0本来就可以直接执行所以初始化时要把所有节点都加进图中。我在模拟题8里遇到的坑是输入格式不是[a, b]数组而是一行字符串类似1-2, 2-3。第一次写的时候没做字符串解析直接处理数组了结果在本地跑得好好的一提交就报格式错误。所以第三题真正难的不是算法而是输入解析。如果你用Java记得ArrayDeque比LinkedList快很多用C的话vectorint graph[n]在节点数特别大时可能出问题建议用vectorvectorint。机试里数据规模通常不会太大但这些小习惯能让你少踩很多坑。4. 机试中的输入输出陷阱与调试技巧4.1 多行输入的处理模式华为机试和LeetCode最大的不同就是LeetCode已经把函数签名和参数传好了而机试需要你自己处理标准输入输出。这个差异让很多人第一次考试时直接崩溃。模拟题8的第三题就是这样输入格式是多行的第一行是任务数第二行开始是依赖关系。处理多行输入我推荐一个通用模板import sys def main(): lines sys.stdin.read().strip().splitlines() if not lines: return # 第一行解析任务数 n int(lines[0].strip()) # 后续行解析依赖关系 for line in lines[1:]: if not line.strip(): continue a, b map(int, line.strip().split()) # 处理...核心是sys.stdin.read()它一次性读取全部输入再按行处理这样就不会因为某一行末尾有空格或者空行而出错。用input()逐行读在输入行数多的时候容易出问题所以能一次 read 就一次 read。4.2 千万不要忽略的边界条件我总结了模拟题8和历次机试里最容易丢分的几个边界输入为空或首行只有回车直接返回。数组只有一个元素动态规划初始值就是答案。数字超过 int 范围尤其是乘积类题目Python 没这个问题但 Java 和 C 要用 long。字符串里有空格、制表符split 时要注意。依赖关系里有重复边影响入度统计最好先去重或用 set 处理。很多人机试挂掉不是算法不行而是这些边界没处理。应对方法很简单写代码前先在草稿纸上列一个“特殊输入清单”一个个验证自己的实现再开始写。4.3 本地IDE和线上评测环境的差异我见过最惨的情况是本地IDE跑得好好的一提交到线上就编译错误。后来发现是本地Java版本和线上版本不一致用了var或者一些新API线上不认。所以备考阶段我强烈建议你装一个和你报考系统接近的编译器版本别用最新版。另外Python 的版本也最好固定比如 3.8 或 3.9避免使用过于新奇的语法。线上环境一般不会开启python-dotenv之类的第三方库所以尽量只用标准库collections、sys、math、re这些已经够用了。还有一个细节线上评测的程序入口。华为OD机试通常要求你提交一个完整的类或脚本类名、方法签名必须严格符合题目要求。如果你提交的是class Main记得public static void main别写错。我在本地测试的时候会写一个脚本批量生成测试用例然后把输出和标准答案比对比如这样python3 solution.py input.txt output.txt diff output.txt expected.txt这个流程虽然简单但在模拟题8的练习里救了我很多次尤其是字符串解析这种容易“眼瞎”的题目。5. 复盘模拟题8时最容易踩的坑5.1 审题不清样例过了不等于能得分模拟题8第一题的样例是2[a3[b]]输出abbbabbb。我第一遍做的时候样例很快过了心里还挺高兴。结果一提交发现只对了一半因为我的代码没有处理0这个数字。题目里明确写了数字可能为00[abc]表示空串。我当时读题的时候直接无视了这句话觉得 “0次重复怎么可能考”结果就栽了。这种“样例过但WA”的情况背后原因几乎都是审题不细。我的对策是把题目描述先读三遍把每一个示例都手动推导一遍再对照自己的理解。尤其是数字范围、数组长度、输出格式这些通常都写在题目最后但恰恰是大家最容易跳过的部分。5.2 暴力枚举超时的判断依据有人问我为什么不能直接暴力答案是数据规模不允许。模拟题8的第二题数组长度如果到十万O(n²) 就是百亿次运算肯定超时。判断暴力会不会超时有一个粗略经验机试的时限通常是1到2秒Python大约每秒能跑一千万到五千万次简单运算。如果数据规模是10^4O(n²) 就是10^8次Python已经很危险如果到10^5那就别想了必须想优化。所以我拿到题的第一件事不是想“怎么暴力”而是先看数据范围再决定算法。LeetCode刷题习惯好的人通常都会看 constraints这个习惯在华为机试里同样重要。5.3 错误提交的影响与策略模拟题8是在一个第三方模拟平台上做的每道题可以重复提交但如果你在真实考场上频繁提交每一分每一秒都在浪费时间。真实机试的环境我没有完全摸透但我的策略一直是先在本地把所有能想到的测试用例都跑一遍确认无重大bug再提交。尤其是第三题这种“局部正确容易全对难”的题我会先提交一个保证能过前两个用例的版本拿到部分分数再继续优化。机试的得分逻辑是“按通过测试点的多少给分”所以你交一个半成品可能比不交强很多但前提是不能因为输出格式错误直接判零分。我在模拟题8上试过这个策略结果是第三题先交了个暴力版本过了部分点再花十分钟改成拓扑排序版本又拿了一部分分。虽然过程有点狼狈但总分比第一次直接死磕强了不少。6. 从模拟题8延伸出的刷题路线与准备节奏6.1 按考点分类整理模板很多人刷题是“东一榔头西一棒子”今天做个链表明天做个回溯后天又去搞图论。这种刷法效率很低因为知识点没有形成体系。我的做法是准备一个笔记按考点整理模板华为机试最常见的几个考点输入输出处理模板sys.stdin.read()、Scanner、cin二叉树遍历模板前中后序、层序动态规划常用状态定义子序列、背包、区间图论建图与遍历邻接表、DFS、BFS、拓扑排序字符串处理常用APIsplit、join、replace、正则排序与自定义比较器尤其是按多关键字排序模拟题8的三道题正好覆盖了字符串、DP、图论三个模板区。每做完一套模拟题我都会把新学到的套路补进笔记而不是直接扔到收藏夹吃灰。6.2 每周模拟考试的执行细节如果距离机试还有四周以上我的建议是每周安排一次完整的模拟考试严格执行时间限制比如150分钟中间不暂停、不查资料。模拟题8这类试卷就非常适合用来当周测。具体执行细节有三点定一个安静环境手机静音模拟真实考场的双机位状态。时间到了就停笔把每道题的得分记下来。复盘时不要只看错题要把“卡住的那几十分钟”单独拎出来分析是读题慢还是某个知识点不熟还是调试方式有问题。我坚持了三周发现第一题的平均完成时间从一开始的25分钟压缩到了10分钟第二题和第三题的正确率也有明显提升。有时候刷题数量不是关键定期的限时模拟和复盘才是把能力转化成分数的加速器。6.3 做题顺序与时间分配的实战建议华为机试三道题的难度分布不是绝对的有时候第二题比第三题还难。所以我的做题顺序是第一遍快速扫读三道题花两分钟判断难度。先做最稳的送分题保证拿满基础分。再做有思路但需要调试的中等题给自己留足时间。最后做最难的那道能拿多少拿多少。千万不要在第一题上死磕太久也不要在第三题开头就被“看起来很难”吓住。模拟题8里最让我意外的就是第三题一看要输出执行顺序我以为是复杂的贪心结果仔细读题发现只是拓扑排序。很多时候“难”只存在于题干里不在算法里。另外如果一道题写了二十分钟还没推进果断跳到下一道。机试是拿分游戏不是单题挑战把时间花在最容易得分的环节才是最理性的选择。最后说点我自己的感受。华为机试备考这条路最容易焦虑的就是“感觉题永远刷不完”。但你把模拟题8这种仿真卷吃透之后会发现出题人的套路其实非常有限字符串、DP、图论、输入输出翻来覆去就这些东西。真正让你丢分的地方往往不是你不会动态规划而是你没看清边界、没有处理输入格式、或者被嵌套字符串的栈结构绕晕了。每次考完把丢分的地方归类一下你会发现下一次考试时踩坑的概率会肉眼可见地下降。希望这篇关于模拟题8的复盘能让你在备考路上少走几步弯路。 
长河君 · 2026/8/31 5:14:57 · 阅读 1.2k 华为机试模拟题8复盘：字符串、动态规划与拓扑排序实战
你们有没有那种感觉刷题刷到第8套模拟题的时候突然意识到前面7套都白刷了。我第一次做华为机试编程模拟题8的时候愣是看着一道字符串题发了十分钟呆。倒不是题目有多难而是它把很多平时刷题时忽略的细节全揉在一起比如输入格式的坑、边界条件的判定、还有那些稍微一变型就认不出来的老题目。这篇文章我就拿模拟题8当引子把华为机试备考里最值得花时间的几个地方完整拆一遍包括题型结构、高频算法考点、具体代码实现、输入输出陷阱还有我踩过的那些坑。我知道关注华为机试的人不少是准备OD机试的也有的是为了校招、保研机试或者单纯想练手。不管你是哪一种模拟题的价值都不在于“背答案”而在于帮你摸清楚出题人的套路。模拟题8这套卷子我前前后后做了三遍每一遍都有新发现。下面我按自己的复盘顺序来讲不整虚的全是实操。1. 模拟题8这套卷子到底在考什么1.1 华为机试的难度定位与考察范围华为机试的难度说高不算高说低也绝对不低。它卡在“校招笔试”和“面试手撕代码”中间比LeetCode的Medium略简单但对时间把控的要求非常高。大部分人不是不会做而是第一题花太多时间导致后面简单题没时间写。考察范围基本固定在四块字符串处理、线性表数组、链表、栈、队列、动态规划、简单图论。很少出现特别偏的算法什么后缀数组、网络流、计算几何基本不会考。但这不代表你可以不准备因为每道题都会在基础题上套一层业务场景比如“日志解析”“资源分配”“任务调度”本质是算法题但披了一层壳。模拟题8尤其明显三题分别对应了字符串模拟、动态规划、图论拓扑难度梯度也拉得比较开第一题送分第二题要仔细第三题是拉分题。我第一次做这套卷子第一题用了二十分钟第二题写了半天没全对第三题只过了样例最后总分惨不忍睹。但恰恰是这种“被虐”的感觉让我后面真正上考场的时候稳了很多。1.2 题型结构与分值分布华为OD机试一般情况下是三道题总分400分常见分值是第一题100分、第二题100分、第三题200分整体通过要求通常看总分是否达标。模拟题8也是按这个结构设计的。第一题是纯字符串处理属于“你只要读懂题就能做”的类型用来保底。第二题是动态规划需要你自己从描述里抽象出状态模型属于区分选手的分水岭。第三题是任务调度相关考察拓扑排序和图建模能力难度比前面高一个档次它的用例比较多光靠暴力往往过不全。有几点要注意华为机试的算分逻辑不是按测试点比例给分的而是按照“通过率”和“边界处理”来评定。也就是说你写了一堆代码但只过了最简单的一个例子很可能拿不到多少分。反过来如果你能把边界情况全考虑进去哪怕算法不是最优解也能拿不错的分。这个特性在后文会反复出现。1.3 和真实OD机试C卷的对比现在大家讨论比较多的是OD机试新系统、双机位监考和C卷。新系统意味着考试环境更规范双机位则一定要提前调试好设备别等到考试当天才发现摄像头不对。至于C卷的题目风格我练完模拟题8再对比网上流传的真题题库目录发现模拟题8的命题思路和C卷高度一致题干长、场景杂、边界多。比如它会给你一段日志里面有几条记录每条记录的字段有缺失让你判断哪些合法或者给你一个依赖关系表让你计算某个任务能不能执行。这种题目在牛客网和LeetCode上很难找到完全一致的只有靠平时积累“读题抽象”的能力。所以如果你时间有限与其刷几百道LeetCode不如集中刷几套仿真模拟题把每一道题的出题套路吃透。模拟题8就是我用来“摸底”的最佳工具。2. 先把高频算法考点的底层逻辑弄清楚2.1 字符串处理与正则表达式的边界华为机试十道题里至少有四道和字符串有关字符串处理的核心不是背API而是理解“边界”。拿模拟题8的第一题举例题目是字符串解压格式类似3[ab]2[c]要输出abababcc。这种题看着简单但面试和机试里最容易丢分的就是括号嵌套、数字重复次数为0、空字符串这些情况。在Python里很多人第一反应是用正则re.findall去提取数字和括号但正则写起来要考虑嵌套关系反而不如手写栈来得稳。我会在第三部分给出完整的栈解法这里先强调一个原则任何字符串处理题都要先想清楚“特殊输入”是什么比如空串、单个字符、嵌套多层、数字后有空格等。把边界全列出来再动手写代码。2.2 栈和队列在括号匹配、单调栈中的应用栈是机试里性价比最高的数据结构。它不仅能做括号匹配还能做表达式求值、最小栈、单调栈等。模拟题8里的字符串解压本质就是一个栈问题遇到数字就记录重复次数遇到[就把当前字符串压栈遇到]就出栈并重复拼接。我经常用一个生活类比来解释栈就像一摞盘子你只能从最上面拿起或放下。字符串嵌套时越晚出现的左括号越早被闭合这天然符合栈的后进先出特性。所以一旦看到“嵌套”“闭合”“回溯依赖”这些词优先想到栈。单调栈在华为机试里也出现过典型题目是“柱状图中最大的矩形”和“每日温度”。这类题的难点不是栈本身而是你得能想到用单调栈来把 O(n²) 优化成 O(n)。如果平时没练过考场上是很难临场推导出来的。所以模拟题8之外建议再单独练十几道单调栈题形成肌肉记忆。2.3 动态规划的核心状态定义与转移方程动态规划是华为机试的第二题常客也是大多数人最头疼的部分。我见过很多人的问题是代码写了上百行但状态定义一开始就错了后面全都白搭。学动态规划最重要的不是背模板而是掌握两个动作定义状态、写转移方程。比如模拟题8的第二题求连续子数组的最大乘积。这个题和最大子段和很像但难点在于负数两个负数相乘可能变成正数所以不能只维护一个最大值得同时维护当前位置能取到的最大值和最小值。状态定义是dp_max[i]表示以第 i 个元素结尾的子数组的最大乘积dp_min[i]表示以第 i 个元素结尾的子数组的最小乘积。转移时当前元素 nums[i] 可能单独成段也可能和前面的段拼接所以dp_max[i] max(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])dp_min[i] min(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])这个转移方程为什么这么写因为乘积的符号会变最大值可能来自“之前的最大值 × 当前正数”也可能来自“之前的最小值 × 当前负数”。把这个想通了动态规划就没有那么神秘。2.4 图论与拓扑排序的题目识别模拟题8的第三题是任务调度这类题在华为机试里出现频率不低因为华为很多产品场景本身就涉及任务编排、依赖关系、资源调度。识别图论题的方法很简单题干里出现“依赖”“先后顺序”“不能同时执行”“循环引用”等关键词就要往有向图方向想如果题目要求判断是否有环、能否完成所有任务那就要上拓扑排序。拓扑排序的Kahn算法核心就是用入度数组和队列。先把所有入度为0的节点入队然后逐个出队把出队节点指向的节点的入度减1减到0就继续入队。如果最后出队节点数不等于总节点数说明图里有环。这个算法的空间复杂度是 O(VE)时间复杂度也是 O(VE)在机试的输入规模下完全够用。重点要注意的是节点编号可能不是从0开始而是从1开始或者带字母处理的时候要建好映射关系。3. 模拟题8重点题目的完整解题思路与代码实现3.1 第一题字符串解压题目描述大致是给定一个压缩后的字符串形如3[ab]2[c]数字表示方括号内字符串重复的次数支持嵌套例如2[a3[b]]解压后是abbbabbb。输出解压后的完整字符串。我自己的实现思路是用两个栈一个存字符串一个存数字遍历字符串遇到数字时把完整数字拼接出来因为可能是多位比如12[a]。遇到字母时拼到当前字符串上。遇到[时把当前字符串和数字分别压入栈然后重置。遇到]时弹出数字和之前的字符串把当前字符串重复数字次然后拼到之前的字符串后面。代码用Python写出来非常直观def decode_string(s: str) - str: num_stack [] str_stack [] cur_str i 0 n len(s) while i n: ch s[i] if ch.isdigit(): num 0 while i n and s[i].isdigit(): num num * 10 int(s[i]) i 1 num_stack.append(num) continue elif ch [: str_stack.append(cur_str) cur_str elif ch ]: repeat_times num_stack.pop() prev_str str_stack.pop() cur_str prev_str cur_str * repeat_times else: cur_str ch i 1 return cur_str这段代码有两个细节值得说。第一是数字处理很多人直接用int(ch)导致多位数字出错第二是cur_str prev_str cur_str * repeat_times这个顺序一定不能写成cur_str * repeat_times prev_str否则嵌套的拼接顺序就反了。我第一遍做就栽在这个顺序上样例怎么调都不对。这类题的复杂度是 O(S)S 是解压后的字符串长度。如果嵌套特别深递归写法可能栈溢出所以用显式栈更稳。机试环境一般不限制递归深度但判断不严还是建议养成用栈的习惯。3.2 第二题连续子数组的最大乘积题目描述给定一个整数数组求所有连续子数组中乘积最大的值。数组长度最大可能就是十万级别所以 O(n²) 暴力是肯定过不了的。我在2.3节已经讲了动态规划的状态定义这里直接给完整实现def max_product(nums): if not nums: return 0 dp_max nums[0] dp_min nums[0] result nums[0] for i in range(1, len(nums)): if nums[i] 0: dp_max, dp_min dp_min, dp_max dp_max max(nums[i], dp_max * nums[i]) dp_min min(nums[i], dp_min * nums[i]) result max(result, dp_max) return result这里用了一个小技巧当nums[i]为负数时交换dp_max和dp_min。因为乘以负数会翻转大小关系交换之后dp_max * nums[i]就变成了原来的“最小值在当前负数下能达到的最大值”逻辑更简洁也避免了写三参数 max 带来的混乱。这种写法在LeetCode上也算标准解但放到华为机试里要注意输入可能包含0。有0的时候乘积会归零此时dp_max可能变成0但这不会影响最终结果因为后面正数还能重新开始。如果你实现的是“必须连续”的版本一定要把0单独作为候选值考虑进去。3.3 第三题任务调度与依赖关系题目描述有 n 个任务编号从 0 到 n-1给定若干依赖关系[a, b]表示任务 b 依赖任务 a也就是要先完成 a 才能完成 b。请判断是否可能存在一种执行顺序让所有任务都能完成如果可以输出任意一种顺序。这不就是拓扑排序的裸题吗Kahn算法直接上from collections import deque def can_finish(num_tasks, prerequisites): graph [[] for _ in range(num_tasks)] indegree [0] * num_tasks for a, b in prerequisites: graph[a].append(b) indegree[b] 1 q deque() for i in range(num_tasks): if indegree[i] 0: q.append(i) order [] while q: node q.popleft() order.append(node) for neighbor in graph[node]: indegree[neighbor] - 1 if indegree[neighbor] 0: q.append(neighbor) if len(order) ! num_tasks: return [] # 存在环无法完成 return order这段代码最容易被忽略的地方是num_tasks和实际出现的节点编号可能不一致。有些题目输入里依赖关系只包含部分任务还有一些任务没出现在依赖关系中此时它们入度为0本来就可以直接执行所以初始化时要把所有节点都加进图中。我在模拟题8里遇到的坑是输入格式不是[a, b]数组而是一行字符串类似1-2, 2-3。第一次写的时候没做字符串解析直接处理数组了结果在本地跑得好好的一提交就报格式错误。所以第三题真正难的不是算法而是输入解析。如果你用Java记得ArrayDeque比LinkedList快很多用C的话vectorint graph[n]在节点数特别大时可能出问题建议用vectorvectorint。机试里数据规模通常不会太大但这些小习惯能让你少踩很多坑。4. 机试中的输入输出陷阱与调试技巧4.1 多行输入的处理模式华为机试和LeetCode最大的不同就是LeetCode已经把函数签名和参数传好了而机试需要你自己处理标准输入输出。这个差异让很多人第一次考试时直接崩溃。模拟题8的第三题就是这样输入格式是多行的第一行是任务数第二行开始是依赖关系。处理多行输入我推荐一个通用模板import sys def main(): lines sys.stdin.read().strip().splitlines() if not lines: return # 第一行解析任务数 n int(lines[0].strip()) # 后续行解析依赖关系 for line in lines[1:]: if not line.strip(): continue a, b map(int, line.strip().split()) # 处理...核心是sys.stdin.read()它一次性读取全部输入再按行处理这样就不会因为某一行末尾有空格或者空行而出错。用input()逐行读在输入行数多的时候容易出问题所以能一次 read 就一次 read。4.2 千万不要忽略的边界条件我总结了模拟题8和历次机试里最容易丢分的几个边界输入为空或首行只有回车直接返回。数组只有一个元素动态规划初始值就是答案。数字超过 int 范围尤其是乘积类题目Python 没这个问题但 Java 和 C 要用 long。字符串里有空格、制表符split 时要注意。依赖关系里有重复边影响入度统计最好先去重或用 set 处理。很多人机试挂掉不是算法不行而是这些边界没处理。应对方法很简单写代码前先在草稿纸上列一个“特殊输入清单”一个个验证自己的实现再开始写。4.3 本地IDE和线上评测环境的差异我见过最惨的情况是本地IDE跑得好好的一提交到线上就编译错误。后来发现是本地Java版本和线上版本不一致用了var或者一些新API线上不认。所以备考阶段我强烈建议你装一个和你报考系统接近的编译器版本别用最新版。另外Python 的版本也最好固定比如 3.8 或 3.9避免使用过于新奇的语法。线上环境一般不会开启python-dotenv之类的第三方库所以尽量只用标准库collections、sys、math、re这些已经够用了。还有一个细节线上评测的程序入口。华为OD机试通常要求你提交一个完整的类或脚本类名、方法签名必须严格符合题目要求。如果你提交的是class Main记得public static void main别写错。我在本地测试的时候会写一个脚本批量生成测试用例然后把输出和标准答案比对比如这样python3 solution.py input.txt output.txt diff output.txt expected.txt这个流程虽然简单但在模拟题8的练习里救了我很多次尤其是字符串解析这种容易“眼瞎”的题目。5. 复盘模拟题8时最容易踩的坑5.1 审题不清样例过了不等于能得分模拟题8第一题的样例是2[a3[b]]输出abbbabbb。我第一遍做的时候样例很快过了心里还挺高兴。结果一提交发现只对了一半因为我的代码没有处理0这个数字。题目里明确写了数字可能为00[abc]表示空串。我当时读题的时候直接无视了这句话觉得 “0次重复怎么可能考”结果就栽了。这种“样例过但WA”的情况背后原因几乎都是审题不细。我的对策是把题目描述先读三遍把每一个示例都手动推导一遍再对照自己的理解。尤其是数字范围、数组长度、输出格式这些通常都写在题目最后但恰恰是大家最容易跳过的部分。5.2 暴力枚举超时的判断依据有人问我为什么不能直接暴力答案是数据规模不允许。模拟题8的第二题数组长度如果到十万O(n²) 就是百亿次运算肯定超时。判断暴力会不会超时有一个粗略经验机试的时限通常是1到2秒Python大约每秒能跑一千万到五千万次简单运算。如果数据规模是10^4O(n²) 就是10^8次Python已经很危险如果到10^5那就别想了必须想优化。所以我拿到题的第一件事不是想“怎么暴力”而是先看数据范围再决定算法。LeetCode刷题习惯好的人通常都会看 constraints这个习惯在华为机试里同样重要。5.3 错误提交的影响与策略模拟题8是在一个第三方模拟平台上做的每道题可以重复提交但如果你在真实考场上频繁提交每一分每一秒都在浪费时间。真实机试的环境我没有完全摸透但我的策略一直是先在本地把所有能想到的测试用例都跑一遍确认无重大bug再提交。尤其是第三题这种“局部正确容易全对难”的题我会先提交一个保证能过前两个用例的版本拿到部分分数再继续优化。机试的得分逻辑是“按通过测试点的多少给分”所以你交一个半成品可能比不交强很多但前提是不能因为输出格式错误直接判零分。我在模拟题8上试过这个策略结果是第三题先交了个暴力版本过了部分点再花十分钟改成拓扑排序版本又拿了一部分分。虽然过程有点狼狈但总分比第一次直接死磕强了不少。6. 从模拟题8延伸出的刷题路线与准备节奏6.1 按考点分类整理模板很多人刷题是“东一榔头西一棒子”今天做个链表明天做个回溯后天又去搞图论。这种刷法效率很低因为知识点没有形成体系。我的做法是准备一个笔记按考点整理模板华为机试最常见的几个考点输入输出处理模板sys.stdin.read()、Scanner、cin二叉树遍历模板前中后序、层序动态规划常用状态定义子序列、背包、区间图论建图与遍历邻接表、DFS、BFS、拓扑排序字符串处理常用APIsplit、join、replace、正则排序与自定义比较器尤其是按多关键字排序模拟题8的三道题正好覆盖了字符串、DP、图论三个模板区。每做完一套模拟题我都会把新学到的套路补进笔记而不是直接扔到收藏夹吃灰。6.2 每周模拟考试的执行细节如果距离机试还有四周以上我的建议是每周安排一次完整的模拟考试严格执行时间限制比如150分钟中间不暂停、不查资料。模拟题8这类试卷就非常适合用来当周测。具体执行细节有三点定一个安静环境手机静音模拟真实考场的双机位状态。时间到了就停笔把每道题的得分记下来。复盘时不要只看错题要把“卡住的那几十分钟”单独拎出来分析是读题慢还是某个知识点不熟还是调试方式有问题。我坚持了三周发现第一题的平均完成时间从一开始的25分钟压缩到了10分钟第二题和第三题的正确率也有明显提升。有时候刷题数量不是关键定期的限时模拟和复盘才是把能力转化成分数的加速器。6.3 做题顺序与时间分配的实战建议华为机试三道题的难度分布不是绝对的有时候第二题比第三题还难。所以我的做题顺序是第一遍快速扫读三道题花两分钟判断难度。先做最稳的送分题保证拿满基础分。再做有思路但需要调试的中等题给自己留足时间。最后做最难的那道能拿多少拿多少。千万不要在第一题上死磕太久也不要在第三题开头就被“看起来很难”吓住。模拟题8里最让我意外的就是第三题一看要输出执行顺序我以为是复杂的贪心结果仔细读题发现只是拓扑排序。很多时候“难”只存在于题干里不在算法里。另外如果一道题写了二十分钟还没推进果断跳到下一道。机试是拿分游戏不是单题挑战把时间花在最容易得分的环节才是最理性的选择。最后说点我自己的感受。华为机试备考这条路最容易焦虑的就是“感觉题永远刷不完”。但你把模拟题8这种仿真卷吃透之后会发现出题人的套路其实非常有限字符串、DP、图论、输入输出翻来覆去就这些东西。真正让你丢分的地方往往不是你不会动态规划而是你没看清边界、没有处理输入格式、或者被嵌套字符串的栈结构绕晕了。每次考完把丢分的地方归类一下你会发现下一次考试时踩坑的概率会肉眼可见地下降。希望这篇关于模拟题8的复盘能让你在备考路上少走几步弯路。