2019年华为秋招笔试那会儿我还在疯狂刷题阶段。那场笔试一共三道题第一题送分第二题就是这次要聊的“字符串还原”。题目大意是给你一个压缩过的字符串像3[a2[c]]这种让你展开成完整形式。说实话这道题放在今天的大厂笔试里依然高频出现LeetCode 394 就是同一道题只是换了个包装。这篇文章我按自己的回忆把题目复述一遍再给出完整的 Java 实现、OJ 平台上的坑点以及面试官可能追问的变体。无论你是刚学 Java 的学生还是准备跳槽的开发者这道题的思路都值得存一下。1. 题目还原与核心思路拆解1.1 原题长什么样题目大致是这样的输入一个压缩后的字符串压缩规则是数字[重复内容]方括号里的内容需要重复数字指定的次数。重复内容本身可以是普通字母也可以是嵌套的数字[重复内容]也就是说括号可以一层套一层。我按当年遇到的用例把规则说得更具体一些3[a]2[bc]应该输出aaabcbc因为3[a]是aaa2[bc]是bcbc。3[a2[c]]应该输出accaccacc因为先算内层a2[c]得到acc再整体重复 3 次。2[abc]3[cd]ef应该是abcabccdcdcdef注意字母ef不在任何括号里原样保留。数字可能不是一位数比如12[a]这时候要解析出整数 12而不是分别处理字符1和2。括号保证是合法的不需要处理缺失右括号或者括号不匹配的情况。输入是一行字符串输出是展开后的完整字符串。这类题为什么值得拿出来复盘因为它在“中等题”里属于性价比非常高的那种思路不绕代码量也不大但是非常考察基本功。你不仅要会解还要在限定时间内一次写对这比单纯“看过题解”要难一截。1.2 为什么一看到括号就该想到栈字符串里带括号的题目八九不离十要用栈。原因很简单括号天然就有“最近匹配”的特性。你看3[a2[c]]最内层的]匹配的并不是最外层的[而是离它最近的[也就是2[c]的左括号。这种“后出现的左括号先被匹配”的顺序和栈的 LIFO后进先出完全一致。你可以把栈想象成一叠盘子遇到[就往上一摞盘子里放一个标记遇到]就从最顶上拿走一个标记。程序里也是这样扫描到[就把当前需要保留的状态压栈扫描到]就把栈顶的状态弹出来和括号匹配的经典题如出一辙。那为什么不是递归其实递归也能解因为嵌套结构本身就是一个递归结构。但笔试环境下递归的代码虽然短一旦递归深度控制不好或者全局指针处理不仔细容易出现隐蔽 bug。栈解法胜在过程直观、每一步都能在脑内模拟写错了也容易定位。我个人的习惯是笔试现场优先写栈面试聊思路的时候再补递归版本。2. Java实现与核心细节2.1 栈解法完整代码与逐段解读先贴一个可以直接提交到判题系统的版本。主类名用了Main这是绝大多数线上笔试平台的要求等下我会专门讲这个坑。import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Deque; public class Main { public static void main(String[] args) throws IOException { BufferedReader reader new BufferedReader(new InputStreamReader(System.in)); String input reader.readLine(); System.out.println(decode(input)); reader.close(); } private static String decode(String s) { DequeInteger numStack new ArrayDeque(); DequeString strStack new ArrayDeque(); StringBuilder cur new StringBuilder(); int num 0; for (char c : s.toCharArray()) { if (Character.isDigit(c)) { num num * 10 (c - 0); } else if (c [) { numStack.push(num); strStack.push(cur.toString()); cur.setLength(0); num 0; } else if (c ]) { int repeatTimes numStack.pop(); StringBuilder temp new StringBuilder(strStack.pop()); for (int i 0; i repeatTimes; i) { temp.append(cur); } cur temp; } else { cur.append(c); } } return cur.toString(); } }核心逻辑分四块我拆开说。数字字符num num * 10 (c - 0)是累加多位数字的标准写法。比如连续读到1、2先得到 1再得到 1 * 10 2 12。这里有一个隐藏要求数字后面一定跟的是[所以数字累加不会和普通字母混淆。左括号[把当前累计的数字num压入数字栈把当前已经拼接好的字符串cur转成 String 压入字符串栈然后清空cur重置num。为什么要重置因为进入了一个新的括号层这一层的字符串要从零开始拼这一层的重复次数也要重新累计。右括号]从数字栈弹出这一层的重复次数从字符串栈弹出这一层左侧已经拼接好的前缀然后把括号里的内容cur重复若干次追加到前缀后面。这一个动作完成之后当前这一层括号就算处理完了拼接结果重新作为新的cur供更外层继续使用。普通字符直接追加到cur末尾相当于“这一层当前积累的字符串”。这里有一个 Java 特有的细节字符串拼接不要用cur cur temp也不要频繁new String。笔试数据量大的时候String 是不可变对象每次拼接都会生成新的字符串时间和内存都会非常难看。StringBuilder在循环里 append 是更稳的做法尤其嵌套多、重复次数大的用例差距会很明显。复杂度方面设最终展开后的字符串长度为 N遍历输入字符串本身是线性的但每一个输出字符最终都会被写入一次所以时间复杂度是 O(N)。空间上栈中保存的字符串总长度也不会超过 N空间复杂度 O(N)。在面对“结果字符串本来就有多长”的问题时这个复杂度已经是理论最优了。2.2 递归解法面试官更喜欢的另一种打开方式栈能够解决的括号问题递归通常也能解决这道题就是典型。递归的写法在笔试里不如栈稳但面试时拿出来讲能体现你对递归结构的理解。递归思路是这样的定义一个全局下标index每次调用只处理一个“括号块”普通字符直接收集遇到数字就解析出完整整数然后跳过[递归解析内层拿到内层字符串后根据重复次数拼接最后遇到]就返回当前这一层的结果。private static int index 0; private static String decodeRecursive(String s) { StringBuilder cur new StringBuilder(); while (index s.length()) { char c s.charAt(index); if (Character.isDigit(c)) { int num 0; while (index s.length() Character.isDigit(s.charAt(index))) { num num * 10 (s.charAt(index) - 0); index; } index; // 跳过 [ String inner decodeRecursive(s); for (int i 0; i num; i) { cur.append(inner); } } else if (c ]) { index; return cur.toString(); } else { cur.append(c); index; } } return cur.toString(); }这个版本最容易踩的坑是全局变量index没有重置。如果你在一个类里写了这个方法并且被测了多组数据第二次执行时index已经不是 0 了结果必然出错。笔试平台里这道题只跑一次问题不大但如果你把代码拿去做单元测试或者扩展成支持多组输入一定要记得在入口处index 0。递归版的缺点是调用栈会随着括号嵌套深度增加而变深如果题目故意给一个几万层的嵌套Java 默认的线程栈可能会溢出。不过正常笔试题不会这么极端所以面试现场写递归反而显得思路清爽。2.3 边界条件与用例验证我在笔试前整理过一套自测用例提交之前先本地过一遍心里会踏实很多。针对这道题至少要覆盖下面几种情况。输入输出考察点3[a]2[bc]aaabcbc基本拼接和多次重复3[a2[c]]accaccacc多层嵌套12[a]aaaaaaaaaaaa多位数解析abcabc没有任何括号和数字a2[b3[c]]dabcccbcccd字母与嵌套混合0[a]空字符串重复次数为 0 的兼容性0[a]这个用例其实题目不一定会给因为题目通常声明 k 是正整数。但代码里temp.append(cur)执行 0 次结果为空天然兼容所以不需要额外处理。还有一个边界是空字符串输入遍历直接结束返回空串也很自然。我自己在实际测试时发现一个容易忽略的点输入字符串中如果首尾带了多余空格readLine()会原样读进来。很多同学习惯性地调用trim()去空格但这个题目的输入理论上不该有首尾空格所以要不要 trim 看平台。如果题目允许字符串中出现空格trim()反而会把合法字符删掉。稳妥做法是读题、看样例、确认输入格式再决定要不要 trim。3. 华为OJ环境下的Java注意事项3.1 主类名、包名这些基础规则华为笔试用的是牛客网这类线上判题平台Java 提交有一个硬性要求主类必须叫Main而且不能带package语句。这个坑看起来低级但每年都有不少人踩。有的同学在本地 IDE 里习惯了用public class Solution或者从 LeetCode 复制代码下来的时候直接把类名带过来了提交到笔试平台后直接编译错误一分没有。编译错误虽然不算罚时但会浪费你重新提交的次数和时间更重要的是影响心态。还有一个容易被忽略的点不要引入 JDK 之外的第三方库。线上判题环境不会给你装org.apache.commons这种依赖也不要天真的以为可以 import 一个网上看来的工具类。老老实实用标准库java.util.*、java.io.*这些足够应付绝大多数题目。3.2 输入输出与调试信息线上笔试的标准输入输出本质上就是程序从标准输入读数据把结果写到标准输出。这道题只有一行输入所以BufferedReader的readLine()最简单直接。很多 Java 新手习惯用Scanner这个类在刷题时不是不能用但BufferedReader在读取大量数据时性能更好而且代码量并没有增加多少。我通常只写一行模板BufferedReader reader new BufferedReader(new InputStreamReader(System.in)); String input reader.readLine();如果题目有多组输入再配合while ((line reader.readLine()) ! null)去循环读。但要注意这道题如果只有一组输入千万不要画蛇添足写一个while循环去读否则输出会重复导致格式错误。输出方面最终结果用System.out.println(decode(input))输出即可。最忌讳的是把调试信息也一并打出来。我知道很多人喜欢在本地跑的时候打印中间变量比如System.out.println(num num)如果提交前忘了删判题系统会把你所有的输出都算进结果里直接判成“输出格式错误”。这个错误比答案算错更冤。提示本地调试可以随便打印提交前务必检查所有输出语句。我自己的习惯是提交前 CtrlF 搜一下System.out确认只有最后一行的结果输出。3.3 内存和运行时间的隐形门槛华为笔试的内存限制经常卡在 64MB 左右听起来不少但 JVM 启动本身就要占一部分内存。如果代码再频繁创建对象内存很容易告急。这道题里最容易产生大量对象的动作是字符串拼接。如果你用String result result inner这种写法每一次拼接都会产生一个新的 String 对象嵌套很多层时JVM 的 GC 压力会非常大运行时间也会被拖慢。改用StringBuilder之后大部分拼接都在同一个可变对象上完成内存和时间都友好很多。还有一个隐形门槛是运行时间。华为笔试的单题时间限制有时只有 1 秒Java 本身启动就要几百毫秒留给算法的余量不多。所以代码里的循环嵌套、字符串复制这些操作都要谨慎。像这道题时间复杂度已经是 O(输出长度)没有优化空间了那就只能从常数层面入手比如用toCharArray()遍历而不是每次charAt()用ArrayDeque而不是Stack。说到StackJava 里Stack类虽然能用但它继承了Vector所有方法都带同步锁性能不如ArrayDeque。刷题场景下我更推荐ArrayDeque配合push()和pop()使用语义和栈完全一致性能还好一截。4. 笔试现场常见问题与调试记录4.1 数字累加忘记归零这个 bug 我在练习时踩过后来帮别人看代码也见过好几次。问题出在只有一个num变量来记录重复次数时遇到[后如果忘了把num重置为 0下一段数字就会累加到旧值上面。举个例子输入2[3[a]]处理完外层2并进行左括号入栈后如果num没有归零读到内层的3时num会变成23而不是3。这样内层重复次数就完全错了而且这种错误往往不会在简单用例里暴露只有嵌套用例才能测出来。所以我的代码里num 0这句紧跟在入栈之后和清空cur写在一起。你也可以自己规定一个顺序数字只负责累加左括号只负责入栈并重置右括号只负责弹出并拼接。流程单一不容易漏。4.2 多位数字解析出错有的同学第一次写看到[前的数字直接用int num c - 0然后默认数字只有一位。输入3[a]没问题换成12[a]就挂了输出变成了1a2a这种奇怪的东西。多位数字的标准处理是num num * 10 (c - 0)。这有点像读入整数时的“边读边乘 10”你只要记住如果字符是数字就先累加到num不要急着处理括号或字母。等到真正遇到[这个num才是完整的重复次数。还有一个细节是数字解析完紧接着一定是[所以代码里不需要再判断下一个字符是什么。但如果你要处理不合法输入比如12a这种那就要额外设计逻辑了。笔试题目明确说明数字后只有[所以放心写。4.3 本地正常提交0分这种“本地没问题一提交就挂”的案例原因通常集中在几个地方。第一类名不是Main。本地 IDEA 里文件名和类名都可以随意判题平台只认Main。第二使用了第三方库或者 import 了不存在的包。第三调试输出忘了删我在 3.2 里强调过。第四读入方式不对比如用了Scanner.next()读包含空格的输入导致只读到空格前的部分。另外有些平台的输入行尾可能会有\r回车符号readLine()通常能处理掉但如果你用Scanner.nextLine()偶发读到空行可以考虑用BufferedReader.readLine()统一处理。排查这类问题时我一般先把代码里的输出语句全部清一遍再检查类名再检查输入输出函数最后才怀疑算法本身。因为算法问题往往会在本地测试用例里暴露编译错误和输出格式错误才是在线平台特有的。4.4 和LeetCode原题的区别LeetCode 394 和这道题核心解法一模一样但这道题在华为笔试中多了一层“在线判题”的约束。LeetCode 只要求你补全decodeString方法类名、输入输出都不用管笔试平台要求完整的Main类和标准输入输出。很多人从 LeetCode 复制解法后不知道怎么拼成完整程序这就是经验问题了。此外LeetCode 的判题环境内存充足时间限制也更宽松部分解法在本地和 LeetCode 能过到了内存只有 64MB 的笔试平台就超时或超内存。这并不是算法思路错了而是实现层面不够“抠”。所以我建议刷题时凡是 Java 写的题目尽量习惯用StringBuilder和ArrayDeque不要总依赖String拼接和Stack。5. 延伸考点与面试追问5.1 同类高频题这道字符串解码题并不是孤立的它背后的“括号 栈 字符串处理”套路在很多大厂笔试里反复出现。我把相关的几类题列一下准备笔试时可以一起刷。第一类是括号匹配比如判断括号是否合法。这是栈最基础的用法考的是“遇到左括号入栈遇到右括号出栈并检查是否匹配”。第二类是逆波兰表达式求值。表达式里的数字和运算符交替出现遇到运算符就从栈里弹出两个操作数计算再把结果压回去。它和字符串解码一样本质都是“用栈维护中间状态”。第三类是表达式展开比如2 * (3 4)这类带括号的算术表达式求值。比字符串解码多一个运算符优先级问题但核心还是两个栈一个数字栈、一个运算符栈。第四类是字符串行程编码的逆过程比如aaabbc压缩成3a2b1c这种在笔试题里也经常出现思路是双指针或者哈希计数和本题正好互补。如果时间有限我的建议是先刷括号匹配和本题因为它们能覆盖栈最常见的应用场景。逆波兰表达式和表达式求值属于加分项有余力再上。5.2 面试官常见的追加问题这道题如果出现在面试环节而不是笔试面试官大概率会顺着解法往下追问。我遇到过的问题大约有三种。第一种是“能不能不用栈用递归实现”。这就是我在 2.2 里写的版本。面试官想看的是你能否理解嵌套结构本身就是递归结构以及递归出口在哪里。第二种是“复杂度能不能优化”。你要能答出时间复杂度已经是 O(输出长度)因为结果字符串本身就要占据这么多空间不可能再快了。这个结论要心里有数别面试官一问“能不能 O(1)”就慌了。第三种是“反过来让你写编码怎么把一个普通字符串压缩成这种格式”。这个方向稍微有点绕本质是找出连续重复的“块”然后按照数字[内容]的格式输出。写的时候要注意如果压缩后的长度比原字符串还长就不应该压缩否则结果反而更大。我在实际处理这类追问时还有一个经验不要只背解法要把“为什么这么写”讲清楚。比如为什么数字栈和字符串栈要分开因为数字和字符串的作用时机不同一个在[时入栈一个在]时拼接。能把这些细节说透面试官才会觉得你是真的理解而不是背过题。另外不管笔试题怎么变思路框架都是通用的遇到括号类字符串问题先想“由内向外”的处理顺序再想用什么数据结构去模拟这个顺序。栈不是唯一的答案但在绝大多数情况下它是实现起来最稳、最不容易出错的选择。我个人在笔试临近结束检查代码时还会再做一次“空转测试”把整个代码从头读一遍逐行模拟输入字符串3[a]2[bc]的执行过程。这个过程看似浪费时间但能帮我发现很多低级失误比如变量名写错、栈弹出顺序写反、重复次数循环边界少一。做完这一步再提交分数基本不会翻车。