题目描述
思路解析动画文字版
记住这条「i 位 × j 位 → 落在 i+j+1,进位进 i+j」。下面每一帧都在套它,看一遍就懂为什么是这两个位置。
先准备一个长度 6 的格子(全 0)当草稿纸。它从左到右就是乘积从高位到低位每一位的暂存值,相乘的结果会一笔笔加进去。
3 乘 6 得 18。为什么加到第 5 位?因为 num1 第 2 位、num2 第 2 位的权重相乘,正好对应结果从右数的那一位,也就是数组下标 i+j+1 = 5;满十的进位往左一格、放到下标 4。
把 18 加进第 5 位:它原来是 0,相加得 18。本位只能放个位 8,多出来的 1 进位到左边第 4 位(变成 1)。这一格的值就这样被更新了。
3 乘 5 得 15。为什么加到第 4 位?因为 num1 第 2 位、num2 第 1 位的权重相乘,正好对应结果从右数的那一位,也就是数组下标 i+j+1 = 4;满十的进位往左一格、放到下标 3。
把 15 加进第 4 位:它原来是 1,相加得 16。本位只能放个位 6,多出来的 1 进位到左边第 3 位(变成 1)。这一格的值就这样被更新了。
3 乘 4 得 12。为什么加到第 3 位?因为 num1 第 2 位、num2 第 0 位的权重相乘,正好对应结果从右数的那一位,也就是数组下标 i+j+1 = 3;满十的进位往左一格、放到下标 2。
把 12 加进第 3 位:它原来是 1,相加得 13。本位只能放个位 3,多出来的 1 进位到左边第 2 位(变成 1)。这一格的值就这样被更新了。
2 乘 6 得 12。为什么加到第 4 位?因为 num1 第 1 位、num2 第 2 位的权重相乘,正好对应结果从右数的那一位,也就是数组下标 i+j+1 = 4;满十的进位往左一格、放到下标 3。
把 12 加进第 4 位:它原来是 6,相加得 18。本位只能放个位 8,多出来的 1 进位到左边第 3 位(变成 4)。这一格的值就这样被更新了。
2 乘 5 得 10。为什么加到第 3 位?因为 num1 第 1 位、num2 第 1 位的权重相乘,正好对应结果从右数的那一位,也就是数组下标 i+j+1 = 3;满十的进位往左一格、放到下标 2。
把 10 加进第 3 位:它原来是 4,相加得 14。本位只能放个位 4,多出来的 1 进位到左边第 2 位(变成 2)。这一格的值就这样被更新了。
2 乘 4 得 8。为什么加到第 2 位?因为 num1 第 1 位、num2 第 0 位的权重相乘,正好对应结果从右数的那一位,也就是数组下标 i+j+1 = 2;满十的进位往左一格、放到下标 1。
把 8 加进第 2 位:它原来是 2,相加得 10。本位只能放个位 0,多出来的 1 进位到左边第 1 位(变成 1)。这一格的值就这样被更新了。
1 乘 6 得 6。为什么加到第 3 位?因为 num1 第 0 位、num2 第 2 位的权重相乘,正好对应结果从右数的那一位,也就是数组下标 i+j+1 = 3;满十的进位往左一格、放到下标 2。
把 6 加进第 3 位:它原来是 4,相加得 10。本位只能放个位 0,多出来的 1 进位到左边第 2 位(变成 1)。这一格的值就这样被更新了。
1 乘 5 得 5。为什么加到第 2 位?因为 num1 第 0 位、num2 第 1 位的权重相乘,正好对应结果从右数的那一位,也就是数组下标 i+j+1 = 2;满十的进位往左一格、放到下标 1。
把 5 加进第 2 位:它原来是 1,相加得 6。本位只能放个位 6,多出来的 0 进位到左边第 1 位(变成 1)。这一格的值就这样被更新了。
1 乘 4 得 4。为什么加到第 1 位?因为 num1 第 0 位、num2 第 0 位的权重相乘,正好对应结果从右数的那一位,也就是数组下标 i+j+1 = 1;满十的进位往左一格、放到下标 0。
把 4 加进第 1 位:它原来是 1,相加得 5。本位只能放个位 5,多出来的 0 进位到左边第 0 位(变成 0)。这一格的值就这样被更新了。
9 对数字(3×3)两两相乘、逐步进位,全部加完后草稿纸定格成 [0, 5, 6, 0, 8, 8]。因为每一步都做了「本位留个位、进位进左边」,所以现在每个格子都已经是 0~9 的单个数字了。
把格子从左到右连起来是 "056088",最高位是 0(因为乘积没占满 6 位),去掉这个前导 0 得到最终答案 "56088"。绿框就是真正保留下来的那几位。
边界先想清:有 "0" 要特判,否则会得到 "000" 这种带前导 0 的串;其余靠「去前导 0」收尾。
三个高频追问,核心都是「为什么 m+n 够」和「为什么不用最后再统一进位」——都源于每步即时落位的设计。
参考代码
def multiply(num1, num2): if num1 == "0" or num2 == "0": return "0" m, n = len(num1), len(num2) res = [0] * (m + n) # 结果至多 m+n 位 for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): mul = (ord(num1[i])-48) * (ord(num2[j])-48) s = mul + res[i + j + 1] # 加上该位已有值 res[i + j + 1] = s % 10 # 本位留个位 res[i + j] += s // 10 # 进位进左一位 return "".join(map(str, res)).lstrip("0") or "0"复杂度
- 时间:O(m·n),num1 每位都要乘 num2 每位,双重循环 m×n 次
- 空间:O(m+n),一个长度 m+n 的结果数组
易错点
面试追问把动画讲成自己的话
追问为什么结果数组长度取 m+n 就一定够?
追问能不能不开数组、直接用字符串逐位拼?
追问每步都 %10 落位,最后还需要再统一处理进位吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
检测正方形
LeetCode 2013 · 中等 · 沿着 数学 & 几何 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题