LeetCode 770 题解：表达式展开与多项式合并全解析-北京尧图网络

LeetCode 770 在我的刷题笔记里代号是“豆包题”。起这个名字那天我刚打开题目手边正好有一袋豆包心想这种“表达式展开”题撑死半小时就能搞定结果豆包热了三回我才把第一个版本跑通。事后复盘它卡人的地方根本不在算法而在于一道题同时塞进了表达式解析、变量替换、多项式乘法展开、同类项合并以及一套非常拗口的排序规则。任何一环想得不细输出就跟你预期差一个量级。这篇内容不是单纯贴一份能过的代码而是把我从“不知道从哪下手”到“能对着编译错误和答案差异一眼定位问题”的完整过程拆开讲。适合已经刷过基础计算器系列、想挑战 Hard 的选手也适合正在准备面试、想练表达式与数据结构设计的人。1. 先看清楚题目到底在问什么一条表达式、两张替换表、一套输出规则1.1 三种输入和它们各自的“坑”这道题的方法签名是public ListString basicCalculatorIV(String expression, ListString evalvars, ListInteger evalints)输入比基础计算器系列多了一个变量赋值机制。expression是一条合法的表达式包含数字、小写字母开头的变量、、-、*、括号和空格。数字不带前导零变量可以由小写字母开头后面继续跟小写字母和数字比如a1b是一个完整的变量名不能拆成a、1、b处理。evalvars和evalints是配套的两张表evalvars[i]这个名字的变量在整个表达式里要用evalints[i]这个整数替换。这里第一个容易踩的坑是替换发生在化简之前不是最后输出前。如果表达式里有x * x而x 2你必须在看到x的瞬间就把它变成常量2。要是等到合并完同类项、得到x*x这一项后才想起来替换那已经晚了因为x*x是作为“两个变量的乘积项”存在的没法再回溯到数值。我习惯把这两种输入看成两条处理线索一条是“表达式本身的结构”另一条是“变量名到数值的映射”。在代码里映射用一个MapString, Long存起来解析变量 token 时先查表查得到就返回常量多项式查不到才当成自由变量。1.2 输出排序degree 优先、变量字典序次之、常数垫底输出格式是本题最容易被扣分的地方。最终合并完同类项后每个非零项要转成一个字符串按“标准序”排列返回。标准序的规则可以拆成三层先按变量个数从多到少排也就是多项式的 degree次数降序。注意变量是可以重复的a*a*b算 3 个变量degree 是 3。变量个数相同时按变量的字典序升序排。比如 degree 都是 2 的两项a*b排在a*c前面。degree 是 0 的项就是纯常数放在最后。如果整个化简结果为 0也就是没有任何非零项返回空列表[]不能输出一个0。举个例子表达式e 8 - a 5没有变量赋值。合并常数8 5 13剩下的自由变量是-a e。两个单项的 degree 都是 1按变量字典序a在e前面所以结果是[-1*a, 1*e, 13]。还有两个输出格式细节只要这一项不是纯常数系数就必须显式写出来哪怕系数是1或-1也要写1*e、-1*a。纯常数项直接输出数字字符串比如13。常数项为 0 时直接丢弃不参与输出。2. 多项式对象设计为什么一张 Map 能把加减乘和同类项一起搞定2.1 选 key 的细节排序后的变量连乘串拿到题目我第一个想法是把整个表达式当成“多项式”来算。一个多项式本质上就是一堆“变量组合系数”的项比如-2*a*b 3*c 5。所以我直接设计一个Poly类内部用一个MapString, Long存所有项key 是变量组合value 是系数。这个 key 怎么定是整个设计里最影响代码量的一步。我采用的做法是把一个项里出现的所有变量名按字典序排序然后用*连接成字符串作为 key。a*b的 key 就是a*b。b*a排序后也是a*b这样乘法里a*b和b*a自然合并成一项。变量可以重复出现比如a*a*b的 key 是a*a*b不化简成指数形式输出时也是展开写。为什么用字符串而不是ListString当 key字符串可以直接放进HashMap合并两个项的变量组合时把两份变量拼在一起再排序、再join逻辑非常简单。输出时也能直接拼在系数后面。唯一要小心的就是变量名里不会出现*所以用*做分隔符绝对安全。纯常数项怎么办我让它的 key 是空字符串。这样所有运算都可以统一加法就是把系数相加乘法就是把两组变量组合合并。2.2 add / sub / mul 三件套的代码实现Poly类核心就三个静态方法add、sub、mul。每次运算返回一个新对象不在原对象上原地修改这样调试时不容易互相污染。class Poly { // key: 排好序的变量连乘串如 a*bvalue: 系数 MapString, Long terms new HashMap(); Poly() {} Poly(long constVal) { if (constVal ! 0) { terms.put(, constVal); } } // 添加一个单项如果合并后系数为 0就把这一项删掉 void addTerm(String key, long coeff) { terms.merge(key, coeff, Long::sum); if (terms.get(key) 0) { terms.remove(key); } } static Poly add(Poly a, Poly b) { Poly res new Poly(); res.terms.putAll(a.terms); for (Map.EntryString, Long e : b.terms.entrySet()) { res.addTerm(e.getKey(), e.getValue()); } return res; } static Poly sub(Poly a, Poly b) { Poly res new Poly(); res.terms.putAll(a.terms); for (Map.EntryString, Long e : b.terms.entrySet()) { res.addTerm(e.getKey(), -e.getValue()); } return res; } static Poly mul(Poly a, Poly b) { Poly res new Poly(); for (Map.EntryString, Long e1 : a.terms.entrySet()) { for (Map.EntryString, Long e2 : b.terms.entrySet()) { String key combineKey(e1.getKey(), e2.getKey()); long coeff e1.getValue() * e2.getValue(); res.addTerm(key, coeff); } } return res; } // 把两个变量组合串合并成一个排好序的新组合串 static String combineKey(String k1, String k2) { if (k1.isEmpty()) return k2; if (k2.isEmpty()) return k1; String[] v1 k1.split(\\*); String[] v2 k2.split(\\*); String[] all new String[v1.length v2.length]; System.arraycopy(v1, 0, all, 0, v1.length); System.arraycopy(v2, 0, all, v1.length, v2.length); Arrays.sort(all); return String.join(*, all); } }sub的实现有个小细节我没有单独写“取负”而是在遍历第二个多项式时直接把系数取相反数再addTerm。这样减少一次中间对象的创建逻辑也更统一。乘法是 O(n*m) 的双层循环n 和 m 分别代表两个多项式的项数。这里没法优化成更快的多项式乘法因为题目规模本身不大重点是保证正确性。最坏情况下乘法的展开确实可能让项数指数膨胀但这是题目本身的属性不是实现逼出来的。2.3 evalvars 替换必须做在 token 层一个反面例子这是我第一版代码最惨痛的教训。我最初的设计是先解析出完整表达式把所有变量都当作自由变量最后再统一替换evalvars。结果遇到x 2、表达式x * x时化简得到的是 key 为x*x、系数为 1 的单项。这时候我想把x替换成2但x*x里已经有两个x联合在一起了我根本不知道该怎么回代。正确的做法是在parseFactor里读到变量 token 时立刻查evalMap。查到了就返回一个常数多项式Poly(constant)查不到才返回单项式Polykey 就是变量名。这样x * x在x 2时两个因子会分别变成常数2乘法结果直接是常数4整个过程根本不会出现x*x这个 key。这个决策要尽早做因为 evalvars 的初衷就是把某些变量“降维”成常量而降维发生在解析阶段最彻底。3. 递归下降解析器让每个字符都找到自己的归处3.1 三个函数对应三个优先级表达式只有三种运算符 -优先级最低*优先级居中括号优先级最高。所以解析器只需要三层递归不需要搞运算符优先级的通用算法。parseExpr()解析加减法内部调用parseTerm()。parseTerm()解析乘法内部调用parseFactor()。parseFactor()解析基础因子处理括号、数字、变量。这个结构我不依赖 Token 列表直接在一个字符串上用索引pos扫。每次读到或-就继续往右读一个 term再把两个多项式相加或相减读到*就继续往右读一个 factor做乘法。Poly parseExpr() { Poly cur parseTerm(); while (pos s.length() (s.charAt(pos) || s.charAt(pos) -)) { char op s.charAt(pos); pos; Poly rhs parseTerm(); if (op ) { cur Poly.add(cur, rhs); } else { cur Poly.sub(cur, rhs); } } return cur; } Poly parseTerm() { Poly cur parseFactor(); while (pos s.length() s.charAt(pos) *) { pos; Poly rhs parseFactor(); cur Poly.mul(cur, rhs); } return cur; }这个写法和“把中缀表达式转后缀再求值”相比好处是括号天然递归处理不需要运算符栈。坏处是每一层都要小心pos是否越界。不过因为题目保证表达式合法解析到末尾时一定已经消费完整条字符串。3.2 parseFactor 里的三个分支与变量命名的坑parseFactor需要处理三种情况括号、数字、变量。我习惯在开头先处理括号因为括号后面跟的一定是一个完整的表达式。Poly parseFactor() { if (s.charAt(pos) () { pos; Poly inner parseExpr(); pos; // 跳过 ) return inner; } if (Character.isDigit(s.charAt(pos))) { long val 0; while (pos s.length() Character.isDigit(s.charAt(pos))) { val val * 10 (s.charAt(pos) - 0); pos; } return new Poly(val); } // 变量首字符是字母后续可以是字母或数字 int start pos; while (pos s.length() (Character.isLetter(s.charAt(pos)) || Character.isDigit(s.charAt(pos)))) { pos; } String var s.substring(start, pos); if (evalMap.containsKey(var)) { return new Poly(evalMap.get(var)); } Poly p new Poly(); p.addTerm(var, 1); return p; }变量读取的 while 条件里我用的是Character.isLetter和Character.isDigit而不是只判断a到z。题目说明变量由小写字母和数字组成但在代码层面统一用isLetter更稳万一测试里出现大写字母也不会崩。当然题目明确说小写这只是我个人的防御式习惯。还有一个细节数字解析用的是long而不是int。虽然题目给的数值范围不大但多项式乘法展开后系数可能成倍增长用long至少能多扛一阵。3.3 主流程整合一行去掉空格剩下交给递归主方法非常简单把空格清掉建好 evalMap然后让parseExpr去处理整条表达式。public ListString basicCalculatorIV(String expression, ListString evalvars, ListInteger evalints) { for (int i 0; i evalvars.size(); i) { evalMap.put(evalvars.get(i), (long) evalints.get(i)); } s expression.replace( , ); poly parseExpr(); return formatResult(poly); }这里注意expression.replace( , )会把所有空格删掉而题目保证空格只会出现在 token 之间不会出现在变量名内部所以删除空格是安全的。如果题目允许空格出现在字符串字面量里那这套写法就不成立但这里显然不会。4. 从散乱 Map 到有序答案排序 comparator 里的两个优先级的真相4.1 comparator 怎么写得短且不出错Poly里的terms是一张 Map遍历时没有顺序概念。所以我需要把每一项取出来按照题目的标准序排序。排序我不打算用字符串直接比。因为字符串a*b和a*c比较结果是对的但万一出现a*aa和aa*a这种情形直接比字符串会有隐患因为分隔符*和字母的 ASCII 顺序可能干扰比较。干脆把字符串拆回变量数组先按数组长度比也就是 degree 降序长度相同再逐个比较变量字符串。ListMap.EntryString, Long items new ArrayList(poly.terms.entrySet()); items.sort((x, y) - { String[] vx x.getKey().isEmpty() ? new String[0] : x.getKey().split(\\*); String[] vy y.getKey().isEmpty() ? new String[0] : y.getKey().split(\\*); if (vx.length ! vy.length) { return vy.length - vx.length; } for (int i 0; i vx.length; i) { int cmp vx[i].compareTo(vy[i]); if (cmp ! 0) { return cmp; } } return 0; });这段代码有个细节值得说如果两项的变量组合相同说明它们是同一个 key在terms里早被addTerm合并了不可能同时出现在遍历结果里。所以 comparator 走到最后的return 0只是一种防御式写法实际不会触发。4.2 输出格式的三种分支排序结束后要把每一项拼成字符串。根据 key 是否为空走两种完全不同的拼接方式ListString formatResult(Poly poly) { ListMap.EntryString, Long items new ArrayList(poly.terms.entrySet()); items.sort(...); // 上面的 comparator ListString ans new ArrayList(); for (Map.EntryString, Long e : items) { long coeff e.getValue(); if (coeff 0) { continue; } String key e.getKey(); if (key.isEmpty()) { ans.add(String.valueOf(coeff)); } else { ans.add(coeff * key); } } return ans; }这里的coeff * key写法虽然简单却能同时处理正负系数系数是-2key 是a*b拼出来是-2*a*b。系数是1key 是e拼出来是1*e。系数是-1key 是a拼出来是-1*a。注意输出格式要求系数1必须写出来所以不能像数学课本那样省略。纯常数项则直接转字符串不能加*。4.3 本地验证用例表看着答案调比看报错更快这种题最怕“不知道正确答案长什么样”。我整理了几个本地验证过的用例每一组都能覆盖一种常见错误expressionevalvars / evalints期望输出0无[]e 8 - a 5无[-1*a, 1*e, 13]a b - a无[1*b](a b) * (a - b)无[1*a*a, -1*b*b]a * b * c b * a * c * 2无[3*a*b*c](a x) * (b - x)x 2[1*a*b, -2*a, 2*b, -4]((a b) * a) - (a*a a*b)无[]最后一个用例很巧妙(a b) * a展开是a*a a*b后面减掉的正好也是a*a a*b两边抵消成 0所以返回空列表。这是检验“系数为 0 的项必须删除”的极佳用例。(a x) * (b - x)在x 2时先替换再展开(a 2) * (b - 2) a*b - 2a 2b - 4。排序后 degree 为 2 的a*b在最前degree 为 1 的两项中a字典序小于b常数-4垫底。5. 复盘“豆包题”我实际调试时反复踩的坑5.1 五个翻车现场和它们对应的修改第一坑是变量替换时机。我前面已经讲过多遍这里不再展开只强调一句在 parseFactor 读到变量时立刻替换是最安全的方案。第二坑是 key 不排序。我第一次写combineKey时直接a * b没排序结果a*b和b*a被当成两项输出里出现了重复变量组合的不同顺序。这个问题在只有一个乘法时看不出来一旦表达式变长就非常明显。后来我在combineKey里加Arrays.sort(all)同类项合并立刻恢复正常。第三坑是 comparator 写反。我最初先比较字典序再比较 degree结果遇到a*a*b和a*b*b时两项 degree 相同变量序列逐位比较能分出先后但遇到a*a*a和a*b时我按字典序把a*b排到了前面而题目要求先按 degree 降序正确顺序应该是a*a*a在前。这个错误隐蔽在简单用例里直到我用a*a*a a*b做测试才暴露。第四坑是常数项为 0 没有删除。addTerm里虽然写了terms.remove(key)但sub里我最初用terms.put(key, -value)而不是addTerm导致a - a化简后 map 里残留 - 0输出阶段判空时没排除它最后吐出一个0。后来统一改用addTerm处理系数的合并和删除问题消失。第五坑是split(\\*)对空字符串的处理。常数项的 key 是空串直接split(\\*)会返回一个长度为 1、内容是空串的数组导致 comparator 里把常数项误判成 degree 为 1 的变量项。我在排序前加了key.isEmpty()判断把常数项转成长度为 0 的数组才彻底解决。5.2 完整参考代码Java整道题合在一起核心部分并不算长。去掉注释大概 130 行左右。完整结构如下class Solution { int pos; String s; MapString, Long evalMap new HashMap(); public ListString basicCalculatorIV(String expression, ListString evalvars, ListInteger evalints) { for (int i 0; i evalvars.size(); i) { evalMap.put(evalvars.get(i), (long) evalints.get(i)); } s expression.replace( , ); pos 0; Poly result parseExpr(); return formatResult(result); } Poly parseExpr() { Poly cur parseTerm(); while (pos s.length() (s.charAt(pos) || s.charAt(pos) -)) { char op s.charAt(pos); pos; Poly rhs parseTerm(); if (op ) cur Poly.add(cur, rhs); else cur Poly.sub(cur, rhs); } return cur; } Poly parseTerm() { Poly cur parseFactor(); while (pos s.length() s.charAt(pos) *) { pos; cur Poly.mul(cur, parseFactor()); } return cur; } Poly parseFactor() { if (s.charAt(pos) () { pos; Poly inner parseExpr(); pos; return inner; } if (Character.isDigit(s.charAt(pos))) { long val 0; while (pos s.length() Character.isDigit(s.charAt(pos))) { val val * 10 (s.charAt(pos) - 0); pos; } return new Poly(val); } int start pos; while (pos s.length() (Character.isLetter(s.charAt(pos)) || Character.isDigit(s.charAt(pos)))) { pos; } String var s.substring(start, pos); if (evalMap.containsKey(var)) { return new Poly(evalMap.get(var)); } Poly p new Poly(); p.addTerm(var, 1); return p; } ListString formatResult(Poly poly) { ListMap.EntryString, Long items new ArrayList(poly.terms.entrySet()); items.sort((x, y) - { String[] vx x.getKey().isEmpty() ? new String[0] : x.getKey().split(\\*); String[] vy y.getKey().isEmpty() ? new String[0] : y.getKey().split(\\*); if (vx.length ! vy.length) return vy.length - vx.length; for (int i 0; i vx.length; i) { int cmp vx[i].compareTo(vy[i]); if (cmp ! 0) return cmp; } return 0; }); ListString ans new ArrayList(); for (Map.EntryString, Long e : items) { long coeff e.getValue(); if (coeff 0) continue; String key e.getKey(); if (key.isEmpty()) { ans.add(String.valueOf(coeff)); } else { ans.add(coeff * key); } } return ans; } static class Poly { MapString, Long terms new HashMap(); Poly() {} Poly(long constVal) { if (constVal ! 0) terms.put(, constVal); } void addTerm(String key, long coeff) { terms.merge(key, coeff, Long::sum); if (terms.get(key) 0) terms.remove(key); } static Poly add(Poly a, Poly b) { Poly res new Poly(); res.terms.putAll(a.terms); for (Map.EntryString, Long e : b.terms.entrySet()) { res.addTerm(e.getKey(), e.getValue()); } return res; } static Poly sub(Poly a, Poly b) { Poly res new Poly(); res.terms.putAll(a.terms); for (Map.EntryString, Long e : b.terms.entrySet()) { res.addTerm(e.getKey(), -e.getValue()); } return res; } static Poly mul(Poly a, Poly b) { Poly res new Poly(); for (Map.EntryString, Long e1 : a.terms.entrySet()) { for (Map.EntryString, Long e2 : b.terms.entrySet()) { res.addTerm(combineKey(e1.getKey(), e2.getKey()), e1.getValue() * e2.getValue()); } } return res; } static String combineKey(String k1, String k2) { if (k1.isEmpty()) return k2; if (k2.isEmpty()) return k1; String[] v1 k1.split(\\*); String[] v2 k2.split(\\*); String[] all new String[v1.length v2.length]; System.arraycopy(v1, 0, all, 0, v1.length); System.arraycopy(v2, 0, all, v1.length, v2.length); Arrays.sort(all); return String.join(*, all); } } }5.3 如果只能记住三件事第一替换 evalvars 要趁早。解析到变量 token 时就查表别等展开完再想怎么回代。第二key 一定要排好序再合并。变量连乘串不排序同类项就永远合并不干净排序规则再对也白搭。第三输出前过滤系数为 0 的项常数项 key 为空时单独处理。这两条看着是边角料实际上决定了你能不能通过样例。我自己做完这题之后最大的感受是这类“表达式展开”题考的不是某个偏门算法而是把一个复杂问题拆成“解析、运算、排序”三个独立模块的工程感。每个模块都不难难的是在动手前把模块边界想清楚。如果在面试里遇到它哪怕最后没写出全部代码只要能把这一段思路讲完整面试官通常也会很满意。

LeetCode 770 题解：表达式展开与多项式合并全解析

相关推荐

医疗AI训练数据合规管道：LabelStudio与OneTrust集成实践

外卖系统+E升级实战：从单体架构到高并发智能调度

Spring AI集成MCP协议实战：一行配置接入外部工具与生产避坑指南

更多资讯

AI不是搜索框：从数字员工到私有知识库，重塑商业模式

NBA 2000-2020赛季球员数据可视化分析项目复盘与实现要点

在Jetson上用OpenClaw让Chromium自动干活

Vue+PHP搭建体育联赛购票系统：从数据库到防超卖完整解析

接口自动化面试高频问题深度解析：从工具操作到框架设计

百万级互动游戏活动策划：从裂变机制到高并发架构的完整指南

今日更新

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？