★ FEATURED ARTICLE 字符串相乘更准确地说就是 LeetCode 43 题 Multiply Strings。我这两年面人时没少出这道题也反复在刷题群里看人讨论真正能一次写对、边界全过、说出原理的候选人确实不多。大多数人看到题的第一反应是“直接用 int 转一下不就行了”然后被一句“输入可能长达 200 位”噎住。这篇文章想从面试官和刷题人两个视角把这道题背后的竖式乘法原理、两种主流实现、边界处理以及从字符串乘法延伸出去的大数运算体系一次性讲透。不管你是刚接触算法题的新手还是准备跳槽的老兵看完应该都能对这类“模拟手算”的题目有更立体的理解。1. 题目拆解这道题到底在考什么1.1 先看题面为什么不能直接转整数题目描述很简单给定两个以字符串形式表示的非负整数num1和num2返回它们的乘积结果也用字符串表示。要求不能使用任何内置的大整数库也不能直接把输入字符串转成整数运算。这里有个很容易被忽略的考点语言内置的整数类型是有上限的。比如 Java 的int最大约 21 亿long最大约 9.2 乘以 10 的 18 次方Python 的int虽然是无限精度但题目偏不让你用。如果输入是两位 100 位的数字你无论用什么原生整数类型都装不下。所以这道题真正考察的东西说出来其实很朴素你会不会把小学数学的竖式乘法翻译成代码逻辑。它考察的不是高深的算法而是基本的字符串处理、数组操作、进位处理和边界意识。这类题在面试中的出现频率极高因为它能快速筛掉两类人一类是只会调库、不懂底层原理的“API 调用师”另一类是粗心大意、边界情况处理不干净的“差不多先生”。1.2 核心数学模型手工竖式的程序化回忆一下小学学的竖式乘法假设计算 456 乘以 123你不会直接去背 456 乘 123 的口诀而是先算 456 乘 3再算 456 乘 20再算 456 乘 100最后把三次结果错位相加。用更公式化的语言描述把num1的第i位数字记为a_inum2的第j位数字记为b_j则a_i * b_j在最终结果中所处的位置取决于这两个数字各自所在的十进制位。如果两个数字的位数分别是m和n那么乘法的结果位数最多是m n位最少是m n - 1位。这个“结果位数最多是 mn 位”的结论是整个代码实现的基石。比如 99 乘 99 等于 9801是 4 位正好是 2 2而 10 乘 10 等于 100只有 3 位。理解了这一点你就知道为什么很多标准解法会预先分配一个长度为m n的数组存结果。理解了数学原理接下来就是怎么把竖式逻辑变成代码。这一步有两条路线一条是“一步到位”的做法另一条是“先乘后进位”的直译版我们逐一看。2. 两种主流实现卷积法与竖式模拟2.1 卷积法一次遍历同步完成累加与进位我先给出我最推荐掌握的写法很多刷题社区的“标准答案”也是长这样def multiply(num1: str, num2: str) - str: if num1 0 or num2 0: return 0 m, n len(num1), len(num2) res [0] * (m n) for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): mul (ord(num1[i]) - ord(0)) * (ord(num2[j]) - ord(0)) p1, p2 i j, i j 1 total mul res[p2] res[p1] total // 10 res[p2] total % 10 start 0 while start m n and res[start] 0: start 1 return .join(map(str, res[start:]))这段代码的核心逻辑在两层循环里。外层从num1的最低位开始内层从num2的最低位开始也就是从右往左逐位相乘。p1是乘积结果的高位位置p2是低位位置。为什么p2 i j 1因为num1[i]和num2[j]分别处在不同的十进制位上它们的乘积落在结果数组里最低位就是i j 1这个位置。举个例子验证一下计算 123 乘以 45结果是 5535。初始化res [0, 0, 0, 0, 0]。当i 2数字 3、j 1数字 5时mul 15p1 3p2 4把 15 拆成十位 1 和个位 5个位放进res[4]十位加到res[3]。接下来i 2、j 0数字 4mul 12此时res[3]已经有 1total 12 1 13于是res[3]变成 3res[2]加 1。这样循环走完res会变成[0, 5, 5, 3, 5]去掉前导零就是 5535。这个方法妙在哪儿它把“累加”和“进位”合并到了一起。每次计算时先读一下低位的已有值把新乘出来的积加进去再把超过 10 的部分回归到高位一步到位代码干净不容易漏进位。2.2 竖式模拟先逐位填入最后统一进位如果说卷积法是“边乘边进位”那竖式模拟就是“先乘完后整理”。思路更直观先用一个数组把每一位的直接乘积都累加进去最后从低位到高位统一处理一遍进位。def multiply_v2(num1: str, num2: str) - str: if num1 0 or num2 0: return 0 m, n len(num1), len(num2) res [0] * (m n) for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): res[i j 1] (ord(num1[i]) - 48) * (ord(num2[j]) - 48) carry 0 for idx in range(m n - 1, -1, -1): total res[idx] carry res[idx] total % 10 carry total // 10 start 0 while start m n and res[start] 0: start 1 return .join(map(str, res[start:]))这版代码更好理解两层循环只做“乘法结果入座”不管进位。等所有乘出来的数都放好了再从数组末尾往前扫一遍把超过 10 的部分一路往上送。最后carry理论上不会剩超过一位因为res分配了m n个位置最坏情况下首位正好放进位。我用 456 乘以 123 帮你走一遍逻辑先算 6 乘 3 得 18填到res[3]再算 5 乘 3 得 15填到res[2]4 乘 3 得 12填到res[1]。等所有位的乘积都填完数组里的数可能都大于 9最后统一进位后才会变成正常的多位数。2.3 两种方案的对比与选型建议我见过很多人在面试现场纠结用哪种其实两者都能过但风格不同对比维度卷积法竖式模拟法理解难度需要理解索引映射稍绕直观贴近手算过程代码量更短稍长多了统一的进位循环出错概率进位写错位置容易翻车进位逻辑独立不容易漏扩展性可平滑迁移到大数加法适合教学演示我的建议是平时练习两种都写一遍面试时优先写你自己更有把握的那种。如果你对索引映射还不太熟就用竖式模拟逻辑直白写错的概率低。等你想在简历上体现一点算法深度时再聊聊卷积法的位置映射原理也不迟。3. 代码实现与关键细节多语言对照3.1 Python 实现的常见细节Python 版本里有个细节值得单独说ord(num1[i]) - ord(0)和int(num1[i])效果相同但前者是纯字符运算效率更高尤其在字符串长度很大的时候能省掉不少字符解析的开销。另外res数组中的数字可能很大Python 的列表没有类型限制你不用担心里面的数超过某个范围。但在 C 和 Java 里res数组里的数在累加时可能会超过int的范围吗注意因为每一个位置最多存 9 以内的最终结果但中间累加过程可能会累计多位数字的乘积所以在极端情况下res[idx]确实可能超过 32767。稳妥的做法是使用long long或int在 Java 里用int[]即可因为单次累加的数理论上限大约 81 乘以位数200 位的输入最多也就 16200不会超 2 的 31 次方。3.2 Java 与 C 实现要点Java 版本的核心代码逻辑和 Python 完全一致但要注意字符转数字别写错class Solution { public String multiply(String num1, String num2) { if (num1.equals(0) || num2.equals(0)) return 0; int m num1.length(), n num2.length(); int[] res new int[m n]; for (int i m - 1; i 0; i--) { for (int j n - 1; j 0; j--) { int mul (num1.charAt(i) - 0) * (num2.charAt(j) - 0); int p1 i j, p2 i j 1; int total mul res[p2]; res[p1] total / 10; res[p2] total % 10; } } StringBuilder sb new StringBuilder(); int start 0; while (start m n res[start] 0) start; for (int i start; i m n; i) sb.append(res[i]); return sb.length() 0 ? 0 : sb.toString(); } }注意 Java 的charAt返回是char直接减0得到真正的数字值。C 则常写成num1[i] - 0逻辑一致。这类题目在 Java 中容易被坑的一个点是用Integer.parseInt去转换单个字符其实完全没有必要性能也不好。3.3 边界条件与防御性编程清单做字符串题边界条件是最容易失分的地方。我总结了一份自查清单每次写完代码按这个过一遍基本能覆盖所有坑num1 0或num2 0直接返回0否则前导零处理容易出bug。num1 1或num2 1任何数乘 1 等于本身。一位数乘一位数比如9 * 9 81验证结果位数是否符合预期。结果本身是零的情况比如大数乘零确保输出是单个0而不是空串。所有位置运算完之后res数组中可能有多余的高位零跳前导零的逻辑必须放在最后。这些边界在 LeetCode 的测试用例中基本是标配你只要漏一个就会在提交时收到红色的 Wrong Answer。4. 实战调试与高频 bug 实录4.1 Bug 一前导零没有去掉这是出现频率最高的问题。很多人写完两层循环直接就把res数组转成字符串返回结果遇到123乘456的时候输出可能变成056088之类的错误结果。原因在于res数组分配了m n位但实际乘积可能只有m n - 1位最高位就是 0。如果不去掉它输出就会多一个前导零。解决办法就是找到第一个非零的下标从那里开始拼接。这里有一个细节如果全部是零说明整个乘积就是 0你需要在拼接前判断一下。如果你在函数开头已经做了“零值提前返回”那这个兜底逻辑也可以留着当保险。4.2 Bug 二进位写反了位置在卷积法里res[p1] total // 10和res[p2] total % 10两行代码的左右顺序很容易搞混。我见过有人写成res[p1] total // 10把原来的高位值直接覆盖掉结果一塌糊涂。为什么会覆盖因为res[p1]可能之前已经被别的乘法贡献过值了你再把它整个替换掉等于丢了前面的累加结果。正确做法是“加进”而不是“赋给”。同样的道理res[p2]这边用的是赋值因为它负责存本位的最终结果之前的值已经通过total mul res[p2]合并进去了。4.3 Bug 三索引遍历顺序搞反如果你从字符串的左边最高位开始遍历也不是不行但索引映射会变得非常绕。常见错误是以为从左边开始就不用管位权偏移结果低位和高位完全错位输出结果差了好几个数量级。我建议统一从右往左遍历也就是range(m - 1, -1, -1)这种写法。这样num1[i]对应的位权就是10^(m - 1 - i)实现竖式乘法时索引关系非常清晰不容易出错。调试这类题我有个习惯先用测试用例123 * 456手跑一遍确认中间过程的res数组每一步都符合预期再提交。这个小习惯帮我省下了大量反复提交的时间。另外可以配合本地使用 Python 的int做结果校验注意仅用于自测提交代码里不能直接用。4.4 自测用例一份拿来即用的清单我喜欢在本地准备一组固定用例每次写完后跑一遍基本能覆盖所有常见 bug输入预期输出测试点0 * 9990零值提前返回1 * 123456123456乘以 19 * 981一位数进位123 * 45656088普通两位数乘三位数9133 * 00尾数带零99999999999999999999 * 99999999999999999999用 Python int 算出真实值超长输入每一条都有它在测试代码里的价值特别是最后一条Input 20 个 9 乘 20 个 9专门用来验证你的代码不会溢出或者卡死。5. 从字符串相乘延伸开去5.1 大数四则运算体系字符串相乘并不是孤立的一道题它背后是一整套“大数运算”体系。字符串相加415 题、字符串相乘43 题、大数相减、大数相除这些都是面试中常见的变体。你会发现它们的底层思路高度一致模拟人工计算过程用数组存每一位注意进位和借位最后处理前导零。当你把字符串相乘写得滚瓜烂熟之后再去做字符串相加就会觉得非常简单因为那只是乘法的一层循环去掉一个维度而已。大数加法有一个细节从末尾逐位相加维护carry最后别忘了如果carry还等于 1要在结果头部加一位。大数减法稍微复杂点需要先比较两个数的大小保证大减小然后再按位借位。5.2 性能优化与分治算法字符串相乘的常规解法是O(m * n)的复杂度。如果输入的两个数字都有 10 万位这个复杂度就是 100 亿次运算严重超时。这时候就需要更高级的算法。Karatsuba 算法是首个突破O(n^2)的大数乘法算法复杂度为O(n^1.585)。它的核心思想是把两个大数各自拆成高低两段然后利用高斯乘法技巧用 3 次乘法替代 4 次乘法。更极端的场景会用快速傅里叶变换FFT把乘法复杂度降到O(n log n)不过面试中基本不会考到这一步。我的一位在量化公司做基础架构的朋友说他们处理极其庞大的数据序列时经常会用到这类优化的思想虽然日常开发中未必真有人手写 FFT 乘法但理解“用分治降低乘法次数”这种思路对解决其他性能问题很有启发。5.3 大数运算的实际应用场景你可能会想现在什么语言没有大数库Python 的int本身就是无限精度Java 有BigInteger为什么还要学这个这是因为很多底层场景不能引入重量级依赖。比如一些早期的嵌入式系统、区块链代码、密码学库或者某些对内存和性能要求极高的分布式系统模块都需要自己实现大数运算。我自己参与过的一个老项目里就因为引入第三方大数库导致整个包体积膨胀、构建时间变长最后运维同事不得不把关键路径上的大数乘法改成手写版本代码量其实不大但运行效率和包体积明显改善。另外这类题目对工程化思维的训练价值很高拆分问题、设计数据结构、处理边界、最后优化性能这套流程在任何领域的开发里都通用。6. 最后的建议与经验分享我在实际刷题和面试别人的过程中发现字符串相乘这道题最适合用来培养“手算思维”。很多人一遇到这种模拟类问题就慌其实只要退一步想想“我自己在纸上会怎么算”思路基本就打开了。我到现在还记得第一次在纸上画出 123 乘 45 的竖式然后对照代码里p1、p2索引的那一刻有种“原来代码就是数学”的顿悟感。如果你正在准备面试建议把这道题连同字符串相加415、字符串相加 II、大数减法一起练习。先把 Python 版写到默写级别再用 Java 或 C 重写一遍最后把边界用例跑熟。这个过程不用太久但收获比光看题解大得多。最后再分享一个小技巧写完后别急着提交先用上面那份自测清单跑一遍特别是99999999999999999999 * 99999999999999999999这种超长用例。这比任何在线判题系统的反馈都更直观因为你可以在本地打印中间数组完完整整看到每一步进位是怎么发生的。等你把这道题彻底吃透以后遇到任何“模拟手算”的题目都会底气十足。
阅读完成 · 觉得有帮助？
