2019年那个秋天我也和大多数人一样把华为的秋招笔试当成一场硬仗来打。机考系统打开之后倒计时一小时五十分钟三道题屏幕右边的提交按钮亮着紧张感一下子上来。前几天把系列第一篇写完不少读者私信说想多看几道真题的Java实现这篇就按当年的题型整理三道我认为非常有代表性的题目一道字符串嵌套展开、一道工位分配的贪心模拟、一道跳石板的动态规划。它们基本覆盖了华为机考最常见的三类考点——字符串处理、区间调度、DP状态设计也正好对应笔试里由易到难的三档分数。如果你也在准备大厂笔试或者想用Java练手数据结构和常用算法这篇可以直接照着敲一遍。1. 机考那些年题型框架与这套题的选择逻辑华为秋招的在线笔试整体风格这么多年其实一直挺稳的。正常是三道编程题时间大概在一百分钟左右不同批次可能略有差异但节奏都是第一题偏字符串或简单模拟第二题开始引入数据结构应用第三题基本就是搜索或动态规划难度有明显梯度。这种设计导致一个结果前三十分钟能不能拿下第一题直接决定你后面还能不能稳住心态。不少同学觉得华为考的是偏门题其实不是。你去翻历年的复盘点会发现出题人非常偏好工程场景下的数据组织问题——字符串展开、任务分配、资源调度都是高频素材。真正拉开差距的往往不是算法本身有多难而是你能不能快速把业务描述抽象成已知的模型。本篇选的三道题对应关系如下题目题型核心考点预估分数档字符串展开栈 / 递归嵌套结构处理、字符串拼接100分档最少工位分配区间调度排序 优先队列、贪心证明200分档跳石板动态规划状态设计、约数枚举、剪枝300分档这套题是我根据当年笔试的回忆版和同期同学的复盘整理出来的不能保证和每个人遇到的题目一字不差但题型、数据范围、边界陷阱都非常贴近原题。建议你先自己动手写一遍再往下看我的实现这样才能知道自己的盲区在哪里。2. 字符串展开嵌套结构的拆解思路与Java实现2.1 题目长什么样这道题是典型的看着不难写起来一堆边界的题。题目大意给定一个编码字符串格式为k[str]其中 k 是正整数表示花括号里的字符串重复 k 次。编码可以嵌套也就是说str本身也可能是带数字前缀的编码串。要求输出展开后的完整字符串。输入样例3[a2[bc]]输出abcbcabcbcabcbc拆开理解2[bc]得到bcbc然后3[a bcbc]就是abcbcabcbcabcbc。数据范围没有特别大但嵌套层数可以很深数字也可能是多位数比如12[a]。这意味着你不能用简单的正则替换或者记录单个字符的方式去处理必须有一种能处理嵌套的数据结构来维护上下文。2.2 双栈解法把展开过程变成栈的压入与弹出第一次做这道题我第一反应是递归因为嵌套结构天然适合递归。但考场上的第一版代码我用的是双栈因为双栈对当前正在拼哪一层、上一层的字符串是什么、要重复多少次这三个信息管理得很直观。思路是这样的维护两个栈一个存数字numStack一个存字符串strStack一个StringBuilder cur用来累积当前层已经解析出的字符串一个int num用来累积当前正在读取的数字从头到尾扫描字符串遇到数字就累加到num上遇到普通字母字符追加到cur遇到[说明要进入下一层把当前累积到的num和cur分别压栈然后重置这两个变量遇到]说明这一层结束从两个栈里弹出上一层的字符串和本层重复次数把cur重复几次后接到上一层的字符串后面赋值回cur。最终cur.toString()就是答案。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String s sc.nextLine(); System.out.println(decode(s)); } static String decode(String s) { DequeInteger numStack new ArrayDeque(); DequeString strStack new ArrayDeque(); int num 0; StringBuilder cur new StringBuilder(); for (char c : s.toCharArray()) { if (Character.isDigit(c)) { num num * 10 (c - 0); } else if (c [) { numStack.push(num); strStack.push(cur.toString()); num 0; cur new StringBuilder(); } else if (c ]) { int repeat numStack.pop(); String prev strStack.pop(); StringBuilder tmp new StringBuilder(prev); for (int i 0; i repeat; i) { tmp.append(cur); } cur tmp; } else { cur.append(c); } } return cur.toString(); } }两个栈的解法之所以好用是因为它把递归的调用栈显式地表达出来了。numStack相当于记录每一层的循环次数strStack相当于记录每一层的调用现场。你去对比递归写法会发现它们本质是同一件事。2.3 递归解法更贴近字符串嵌套的天然结构如果你对双栈的 cur 重置逻辑不太适应递归可能更好理解。思路就是用一个成员变量idx记录当前扫描到的位置定义一个dfs()表示解析从当前位置开始直到遇到 ] 或字符串结束为止的片段并返回这个片段展开后的字符串。public class Main { static int idx 0; static String s; public static void main(String[] args) { Scanner sc new Scanner(System.in); s sc.nextLine(); System.out.println(decode()); } static String decode() { StringBuilder res new StringBuilder(); int num 0; while (idx s.length()) { char c s.charAt(idx); if (Character.isDigit(c)) { num num * 10 (c - 0); idx; } else if (c [) { idx; String inner decode(); for (int i 0; i num; i) { res.append(inner); } num 0; } else if (c ]) { idx; return res.toString(); } else { res.append(c); idx; } } return res.toString(); } }decode()在遇到[时递归调用自己把嵌套的子串展开后返回在遇到]时返回当前层已经拼好的结果。每个递归层负责一对方括号的范围语法树的结构和递归调用的结构天然对应所以这个版本我后来更喜欢用来做讲解。两个版本的时间复杂度都是 O(n)空间复杂度都是 O(n)。递归可能在嵌套特别深时出现栈溢出但笔试题一般不会那么极端两种写法都能过。2.4 我在考场上栽过的坑这道题我有三个印象特别深的坑估计你也会遇到第一数字必须是多位数累积不是单字符处理。12[a]这种输入如果你只取当前字符转 int得到的是1和2分开处理结果完全错。所以扫描数字时要num num * 10 (c - 0)。第二[之后的 cur 重置不能忘。我第一次写双栈时进入[后没有重置cur结果上层字符串和当前层的首段内容全混在一起输出完全是乱的。[表示上一层的字符串已经入栈保护cur必须重新开始累积新内容。第三]处拼接的顺序。是先取prev再拼重复后的cur顺序反了输出就会变成bcbcabcbcabcbcabc这种。考场上一旦出现这种问题肉眼排查很费时间所以平时写这种拼接逻辑时建议顺手把prev cur * repeat这个顺序默记下来。3. 最少工位分配区间调度的贪心证明与优先队列落地3.1 把业务题翻译成区间重叠模型第二题是一道很华为的业务场景题。题目大意某条生产线上有 N 个加工任务每个任务有一个开始时间和结束时间任务在同一时刻不能共享同一个工位问整条产线最少需要准备多少个工位。输入样例5 1 4 2 3 3 6 5 7 6 8输出为 2因为[1,4]、[2,3]、[3,6]这三个任务在 3 这个时刻重叠最多需要三个工位。本质就是给定一组区间求同一时刻最多有多少个区间重叠。只要把业务词汇剥掉这就是经典的会议室问题。我当时在考场上的第一反应是按开始时间排序后暴力检查重叠数O(n^2) 的复杂度n 如果到 10^5 级别肯定超时。所以一定要想到用优先队列优化。3.2 排序 最小堆的完整实现核心策略先把所有任务按开始时间从小到大排序然后用一个最小堆维护当前正在进行的任务的结束时间。遍历每个任务时看堆顶的任务是否已经结束——如果堆顶结束时间小于等于当前任务的开始时间说明这个工位可以空出来复用把堆顶弹出然后无论如何把当前任务的结束时间放进堆里。最终堆的大小就是同时进行中的任务数量也就是最少需要的工位数量。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[][] tasks new int[n][2]; for (int i 0; i n; i) { tasks[i][0] sc.nextInt(); tasks[i][1] sc.nextInt(); } Arrays.sort(tasks, (a, b) - a[0] - b[0]); PriorityQueueInteger pq new PriorityQueue(); for (int[] t : tasks) { if (!pq.isEmpty() pq.peek() t[0]) { pq.poll(); } pq.offer(t[1]); } System.out.println(pq.size()); } }这段代码非常短但它分裂出两个值得展开的点为什么结束时间最早的一定优先考虑以及为什么用判断复用条件。3.3 为什么对结束时间取最小是最优策略这里必须讲清楚贪心为什么成立不然你换个数字范围又不敢写了。设想你有若干个工位每个工位被一个任务占用。新任务来了你当然希望从已经空出来的工位里挑一个而不是新开工位。如果存在多个可复用工位挑哪一个都一样因为工位本身没有区别。但如果没有工位空出呢那就只能新增。关键点是当多个工位都还没空出时最先结束的工位是最有可能承接下一个任务的。我们用一个最小堆维护所有工位当前的结束时间下一个任务如果能复用一定优先复用最早结束的工位。如果最早结束的工位都来不及空出来那其他工位更不可能空出来此时就只能新开工位。这个先看最早结束的工位的策略是贪心选择性的核心。你可能会问万一我把最早结束的工位复用给了当前任务导致后面一个更紧急的任务没有工位怎么办不会因为任务之间只有时间冲突关系没有优先级关系。谁先开始就先安排谁复用最早结束的空闲工位不会减少总可用工位数也不会让后续任务更难安排。这是一个非常典型的按结束时间最早复用的贪心结构。3.4 两个容易踩的细节第一个细节结束时间和开始时间相等的边界。pq.peek() t[0]里的不是随便写的。如果任务 A 的结束时间等于任务 B 的开始时间比如 A 是[1, 3]B 是[3, 5]那么 A 结束的瞬间 B 开始同一个工位可以无缝交接。这个属于不冲突的。但如果题意改成结束当天还需要半天收尾之类的话就得改成。做题前务必读清楚题目里对时间边界的定义华为有些题就喜欢在这里埋扣。第二个细节优先队列的默认排序。PriorityQueueInteger默认是小顶堆也就是peek()取到的是最小值正好满足我们最早结束的需求。但如果你存的是自定义对象那就必须手写 Comparator或者让类实现Comparable。考场时间紧张时建议直接用PriorityQueueInteger存结束时间这种基础类型避免在比较器上浪费时间。真要用自定义类的话写法类似PriorityQueueTask pq new PriorityQueue((a, b) - a.end - b.end);另外这题如果换成扫描线的思路也能做把所有开始时间标记为 1结束时间标记为 -1排序后累加求最大值。但优先队列的写法更符合工位复用的业务直觉在考场上更容易推出来我推荐优先队列。4. 跳石板DP状态到底是怎么想出来的4.1 题目描述与样例第三题是华为机考里流传很广的一道经典题跳石板。题目大意小明从编号 N 的石板出发要跳到编号 M 的石板。每次跳跃的规则是假设当前所在石板编号为 x那么下一步可以跳到x y其中 y 必须是 x 的一个约数并且 y 不能是 1也不能是 x 本身。也就是说每次只能跳当前编号的真约数这么多步。问从 N 到 M 最少需要跳几次如果无法到达输出 -1。输入样例4 24从 4 出发4 的真约数只有 2所以第一步只能到 6。6 的真约数是 2 和 3可以到 8 或 9。这样逐步往后跳最终到 24 的最少步数是 5。出题人把数学概念约数和最短步数问题结合在一起既考了数论基础又考了动态规划或搜索的建模能力。4.2 为什么这题能直接上DP看到最少步数你可能第一反应是 BFS这没错。但跳石板这题有一个天然适合 DP 的结构每次跳的方向都是朝着编号变大的方向也就是说状态转移是有向无环的。从 x 出发只能到比 x 大的位置永远不会跳回来。所以如果我们从 N 到 M 从左往右递推每个位置的最优解在计算时就已经确定了不会被后面位置影响。这就把问题转化成了典型的一维 DP 求最小步数dp[i]表示从 N 跳到 i 的最少步数初始dp[N] 0其他位置为无穷大对每个 i如果dp[i]可达算出 i 的所有真约数依次更新dp[i 约数] min(dp[i 约数], dp[i] 1)因为状态只从小的 i 流向大的 i所以一趟for循环就能完成全部更新。4.3 从初始状态开始的完整递推代码实现如下import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int INF Integer.MAX_VALUE / 2; int[] dp new int[m 1]; Arrays.fill(dp, INF); dp[n] 0; for (int i n; i m; i) { if (dp[i] INF) { continue; } for (int step : getDivisors(i)) { int next i step; if (next m) { dp[next] Math.min(dp[next], dp[i] 1); } } } System.out.println(dp[m] INF ? -1 : dp[m]); } static ListInteger getDivisors(int x) { ListInteger res new ArrayList(); for (int d 2; d * d x; d) { if (x % d 0) { res.add(d); if (d ! x / d) { res.add(x / d); } } } return res; } }这个递推的核心就在dp[i step] Math.min(dp[i step], dp[i] 1)这一行。每走到一个位置 i如果它可达就尝试所有合法的跳跃步长更新下一步位置的最优值。用样例4 24手动模拟一下初始几步dp[4] 04 的约数是 2更新dp[6] 1i5dp[5]还是 INF跳过i6dp[6] 16 的约数是 2、3更新dp[8] 2dp[9] 2i7质数没有真约数跳过i88 的约数是 2、4更新dp[10] 3dp[12] 3i99 的约数是 3更新dp[12] min(3, 21) 3最终一路更新到dp[24]得到答案 5你可以看到dp[12]被 8 和 9 两条路径同时更新DP 做的就是保留更小的那个步数这正是动态规划最核心的取最优子结构。4.4 约数枚举的性能与边界约数枚举这块很多人会写成从 1 到 x 全遍历一遍那样每个位置都是 O(x)整体复杂度会到 O(M^2)100000 的数据范围直接超时。正确的做法是只枚举到sqrt(x)找到一个约数 d 时顺手把x/d也加上。比如 24遍历 d 从 2 到 4d2 时加上 2 和 12d3 时加上 3 和 8d4 时加上 4 和 6一次搞定所有真约数。注意d * d x时不要重复添加同一个约数比如 25 的约数 5。还有一个容易忽略的坑质数位置没有任何真约数所以一旦跳到质数上就跳不出去了。实际问题里很多位置会因此变成死路dp[i] INF的判断就是用来跳过这些位置的。但质数位置的 INF 状态没有任何问题因为它是从起点不可达的不影响其他位置的正确性。我在考场上的第一次提交就是忘了判断if (dp[i] INF) continue;导致所有不可达位置都参与了计算结果全部溢出成负数那次教训很深刻。如果你偏好 BFS这道题也完全可以用队列做每次从队首位置扩展所有合法跳跃。但 BFS 需要额外维护一个 visited 数组而且空间占用比一维 DP 大不少。DP 的写法更简洁也更符合华为机考喜欢考动态规划的调性所以我推荐优先掌握 DP。5. 华为机考的Java环境细节与临场策略5.1 类名、包名与编译器版本华为机考用的是在线判题系统Java 主类必须命名为Main不能带package声明main方法签名必须是public static void main(String[] args)。这些看起来是常识但每年都有人因为类名不对导致编译失败。编译器版本一般是 JDK 8 或更高版本所以 lambda 表达式和Arrays.sort的比较器写法是可以用的放心用。如果你平时在 IDE 里习惯自动生成包名提交前一定要删掉package那行否则判题系统直接报编译错误。这个错误在本地完全不会出现属于环境差异坑提前知道能省下宝贵的几分钟。5.2 用Scanner还是BufferedReader很多 Java 考生习惯用Scanner因为写起来方便。但如果数据量到了 10^5 甚至 10^6 级别Scanner的nextInt()和nextLine()性能会比BufferedReader慢不少。我一般按数据量大小分成两档数据量小几千行以内Scanner完全够用没必要为难自己数据量大万行以上换BufferedReaderStringTokenizer一个万金油模板import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int m Integer.parseInt(st.nextToken()); // ... } }对于不确定有多少行输入的情况可以这样String line; while ((line br.readLine()) ! null !line.isEmpty()) { StringTokenizer st new StringTokenizer(line); // 逐行处理 }我的习惯是读整数优先用 StringTokenizer读字符串再用BufferedReader.readLine()。这样既避免了Scanner的性能问题又不会因为换行符处理不当丢数据。5.3 机考环境的调试策略华为机考的在线编辑器通常没有完整的代码补全也没有断点调试多数时候只能靠System.out.println打印中间结果。所以我考场上的策略是先保证整体逻辑跑通再追求一次通过。每写完一题先对照题目给的样例跑一遍如果对了再自己构造几个边界数据空输入单个元素最大数据量数值溢出边界比如字符串展开我会测10[a]验证多位数重复跳石板我会测4 4这种起点等于终点的情况。这些边界在判题系统里很常见但自己构造的时候往往想不起来。另外机考环境里System.out.println的输出会实时显示在页面上但提交之后不会作为得分依据所以调试输出不用删除也能过——前提是你的调试输出没有严重拖慢程序。不过保险起见正式提交前还是注释掉比较好避免某些严格判题系统把你多输出的内容也拿去比对。5.4 携带一份自己的模板准备这类笔试我强烈建议在本地准备一份精简的 Java 模板把常用的 import、快速 IO 结构、常见算法模板都写好。考场上时间紧张先打开模板把 IO 框架搭好再开始读题能省下很多敲代码的时间。我的模板大概长这样import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); PrintWriter out new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); StringTokenizer st; // 读取 int int n Integer.parseInt(br.readLine()); st new StringTokenizer(br.readLine()); int a Integer.parseInt(st.nextToken()); int b Integer.parseInt(st.nextToken()); out.println(ans); out.flush(); } }用PrintWriter统一输出有个好处就是最后的out.flush()一次把缓冲区的内容全打出去比一次性拼接大字符串更快也更不容易错。这个模板我后来一直沿用到了所有在线笔试和面试手撕代码的环节。对我来说华为机考最公平的一点是它不问你学历背景只看那一个来小时里你能不能把题目写对。把这三道题真正吃透之后后面再去面其他公司遇到类似的字符串展开、区间调度和 DP 递推我心里都有底很多。备考最忌只背代码建议你拿到题目先自己写一遍再对照这篇的实现看差距在哪里——这个差距才是你真正要补的东西。