京公网安备11010502063487号给定两个用字符串表示的非负整数，返回它们乘积的字符串表示。题目禁止直接使用大整数类型，也不允许把输入直接转成整数相乘，所以要自己实现竖式乘法。做法是：结果最多有 m + n 位（m、n 是两个数的位数），用一个长度 m + n 的数组，让第一个数的第 i 位乘第二个数的第 j 位，乘积落在结果的第 i + j 位（进位）和第 i + j + 1 位（个位）。本文用真实运行展示"直接用内置整数相乘"为什么不行，实测竖式乘法的耗时，给出五种语言的实现，并把每一步的进位做成分步演示。
完整题目见官方页面（链接在文末）。两个数都不含前导 0（除非就是 0 本身）。基准解直接用 Python 的大整数乘法，这在真实的题目里是被禁止的，但对验证结果是可靠的独立写法。一共 15 组用例，覆盖：官方示例、有一个是 0、9 乘 9 的进位、全是 9 的两个数、超过 64 位整数范围的大数、位数差别很大的两个数：
输入 ["2","3"] 输出 "6" 输入 ["123","456"] 输出 "56088" 输入 ["0","0"] 输出 "0" 输入 ["0","12345"] 输出 "0" 输入 ["9","9"] 输出 "81" 输入 ["99","99"] 输出 "9801"
题目里的数最长 200 位，而语言里的普通整数只有 32 位或 64 位，JavaScript 的数字是双精度浮点，只有 53 位有效数字。下面是真实运行的结果：
直接用语言内置整数/浮点数相乘，为什么不行：
Java long: 99999999999 * 99999999999 = 1864711849423024129
正确值: 9999999999800000000001
JS Number: 99999999999999999 * 99999999999999999 = 1e+34
JS BigInt: 99999999999999999 * 99999999999999999 = 9999999999999999800000000000000001
JS Number.MAX_SAFE_INTEGER = 9007199254740991 ；Number("99999999999999999") = 100000000000000000
本文 solve('99999999999', '99999999999') = 9999999999800000000001Java 的 long 相乘：99999999999 × 99999999999 应该是 9999999999800000000001，long 装不下（最大约 9.22 × 10^18），得到了一个完全不对的 1864711849423024129。JavaScript 的 Number 相乘：99999999999999999 超过了 2^53，先被舍入成 100000000000000000，乘积变成 1e+34，精度全部丢失；用 BigInt 可以得到正确结果，但那正是题目要求不能用的。本文的竖式乘法逐位计算，位数不受限制。
结果数组 res 长度 m + n。从两个数的最低位开始，双重循环：第一个数的第 i 位乘第二个数的第 j 位，加上 res[i + j + 1] 里已有的值，个位留在 res[i + j + 1]，进位加到 res[i + j]。因为进位会累加到更高位，但下一轮循环处理更高位时会把它一并处理，所以不需要单独的进位循环。最后去掉前导 0。任一个数是 0 时直接返回 "0"。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(num1, num2): if num1 == "0" or num2 == "0": return "0" m, n = len(num1), len(num2) res = [0] * (m + n) # m 位乘 n 位，乘积最多 m+n 位 for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): s = int(num1[i]) * int(num2[j]) + res[i + j + 1] # 这一位上已有的值，加上本次的乘积 res[i + j + 1] = s % 10 # 个位留在 i+j+1 res[i + j] += s // 10 # 进位加到 i+j（更高一位） k = 0 while k < len(res) - 1 and res[k] == 0: # 去掉前导 0 k += 1 return "".join(map(str, res[k:]))
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON ["2","3"] → "6" ["123","456"] → "56088" ["0","0"] → "0" ["0","12345"] → "0" ["9","9"] → "81" ["99","99"] → "9801"
Java · 解法代码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]; // m 位乘 n 位，乘积最多 m+n 位 for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { int s = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + res[i + j + 1]; res[i + j + 1] = s % 10; // 个位留在 i+j+1 res[i + j] += s / 10; // 进位加到 i+j（更高一位） } } StringBuilder sb = new StringBuilder(); int k = 0; while (k < res.length - 1 && res[k] == 0) k++; // 去掉前导 0 for (; k < res.length; k++) sb.append(res[k]); return sb.toString(); } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl ["2","3"] → "6" ["123","456"] → "56088" ["0","0"] → "0" ["0","12345"] → "0" ["9","9"] → "81" ["99","99"] → "9801"
Go · 解法代码func multiply(num1, num2 string) string { if num1 == "0" || num2 == "0" { return "0" } m, n := len(num1), len(num2) res := make([]int, m+n) // m 位乘 n 位，乘积最多 m+n 位 for i := m - 1; i >= 0; i-- { for j := n - 1; j >= 0; j-- { s := int(num1[i]-'0')*int(num2[j]-'0') + res[i+j+1] res[i+j+1] = s % 10 // 个位留在 i+j+1 res[i+j] += s / 10 // 进位加到 i+j（更高一位） } } k := 0 for k < len(res)-1 && res[k] == 0 { // 去掉前导 0 k++ } out := make([]byte, 0, len(res)-k) for ; k < len(res); k++ { out = append(out, byte('0'+res[k])) } return string(out) }
$ go build -o bin . && ./bin < cases.jsonl ["2","3"] → "6" ["123","456"] → "56088" ["0","0"] → "0" ["0","12345"] → "0" ["9","9"] → "81" ["99","99"] → "9801"
JavaScript · 解法代码function multiply(num1, num2) { if (num1 === "0" || num2 === "0") return "0"; const m = num1.length, n = num2.length; const res = new Array(m + n).fill(0); // m 位乘 n 位，乘积最多 m+n 位 for (let i = m - 1; i >= 0; i--) { for (let j = n - 1; j >= 0; j--) { const s = Number(num1[i]) * Number(num2[j]) + res[i + j + 1]; res[i + j + 1] = s % 10; // 个位留在 i+j+1 res[i + j] += Math.floor(s / 10); // 进位加到 i+j（更高一位） } } let k = 0; while (k < res.length - 1 && res[k] === 0) k++; // 去掉前导 0 return res.slice(k).join(""); }
$ node run.js < cases.jsonl ["2","3"] → "6" ["123","456"] → "56088" ["0","0"] → "0" ["0","12345"] → "0" ["9","9"] → "81" ["99","99"] → "9801"
C++ · 解法代码#include <string> #include <vector> using namespace std; class Solution { public: string multiply(string num1, string num2) { if (num1 == "0" || num2 == "0") return "0"; int m = num1.size(), n = num2.size(); vector<int> res(m + n, 0); // m 位乘 n 位，乘积最多 m+n 位 for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { int s = (num1[i] - '0') * (num2[j] - '0') + res[i + j + 1]; res[i + j + 1] = s % 10; // 个位留在 i+j+1 res[i + j] += s / 10; // 进位加到 i+j（更高一位） } } string out; size_t k = 0; while (k + 1 < res.size() && res[k] == 0) k++; // 去掉前导 0 for (; k < res.size(); k++) out.push_back('0' + res[k]); return out; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl ["2","3"] → "6" ["123","456"] → "56088" ["0","0"] → "0" ["0","12345"] → "0" ["9","9"] → "81" ["99","99"] → "9801"
共 15 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 15/15 Java 通过 15/15 Go 通过 15/15 JavaScript 通过 15/15 C++ 通过 15/15
两个数各 n 位，都是全 9 和全 8 组成（进位最多的情形），每个规模取三次中最快的一次：
每个数的位数 | 暴力解 | 本文解法
100 | 0.002 ms | 1.174 ms
300 | 0.009 ms | 11.456 ms
1000 | 0.085 ms | 135.121 ms
2000 | 0.298 ms | 545.889 ms竖式乘法从 100 位到 300 位（3 倍）耗时增长约 9.8 倍，从 300 到 1000 位（3.3 倍）增长约 11.8 倍，从 1000 到 2000 位增长约 4.0 倍，符合 O(mn) 的平方增长。表中的"暴力解"是 Python 内置的大整数乘法，它是 C 实现，并且使用了更好的算法，所以比在 Python 里逐位循环快得多：2000 位时 0.298ms 对 545.9ms。这个对比说明的是 Python 解释器与 C 的差距，不是竖式乘法的算法有多差。
Python 版本另外和 Python 内置的大整数乘法做了随机对拍，两个数各 1 到 25 位，其中 5% 取 0：
随机对拍 20000 组（两个各 1 到 25 位的随机十进制数（5% 的概率取 0）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 15 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用 123 × 45。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。注意 i=1, j=1 那一步：2 × 5 + res[3] 已有的 3 = 13，个位 3 留在 res[3]，进位 1 加到 res[2]。结果是 5535。