字符串相乘 图解题解

这道题到底在问什么

输入

num1="123", num2="456"

输出

"56088"

最优解：一步一步想明白

1. 3记住这条「i 位 × j 位 → 落在 i+j+1，进位进 i+j」。下面每一帧都在套它，看一遍就懂为什么是这两个位置。
2. 4先准备一个长度 6 的格子（全 0）当草稿纸。它从左到右就是乘积从高位到低位每一位的暂存值，相乘的结果会一笔笔加进去。
3. 53 乘 6 得 18。为什么加到第 5 位？因为 num1 第 2 位、num2 第 2 位的权重相乘，正好对应结果从右数的那一位，也就是数组下标 i+j+1 = 5；满十的进位往左一格、放到下标 4。
4. 6把 18 加进第 5 位：它原来是 0，相加得 18。本位只能放个位 8，多出来的 1 进位到左边第 4 位（变成 1）。这一格的值就这样被更新了。
5. 73 乘 5 得 15。为什么加到第 4 位？因为 num1 第 2 位、num2 第 1 位的权重相乘，正好对应结果从右数的那一位，也就是数组下标 i+j+1 = 4；满十的进位往左一格、放到下标 3。
6. 8把 15 加进第 4 位：它原来是 1，相加得 16。本位只能放个位 6，多出来的 1 进位到左边第 3 位（变成 1）。这一格的值就这样被更新了。
7. 93 乘 4 得 12。为什么加到第 3 位？因为 num1 第 2 位、num2 第 0 位的权重相乘，正好对应结果从右数的那一位，也就是数组下标 i+j+1 = 3；满十的进位往左一格、放到下标 2。
8. 10把 12 加进第 3 位：它原来是 1，相加得 13。本位只能放个位 3，多出来的 1 进位到左边第 2 位（变成 1）。这一格的值就这样被更新了。
9. 112 乘 6 得 12。为什么加到第 4 位？因为 num1 第 1 位、num2 第 2 位的权重相乘，正好对应结果从右数的那一位，也就是数组下标 i+j+1 = 4；满十的进位往左一格、放到下标 3。
10. 12把 12 加进第 4 位：它原来是 6，相加得 18。本位只能放个位 8，多出来的 1 进位到左边第 3 位（变成 4）。这一格的值就这样被更新了。
11. 132 乘 5 得 10。为什么加到第 3 位？因为 num1 第 1 位、num2 第 1 位的权重相乘，正好对应结果从右数的那一位，也就是数组下标 i+j+1 = 3；满十的进位往左一格、放到下标 2。
12. 14把 10 加进第 3 位：它原来是 4，相加得 14。本位只能放个位 4，多出来的 1 进位到左边第 2 位（变成 2）。这一格的值就这样被更新了。
13. 152 乘 4 得 8。为什么加到第 2 位？因为 num1 第 1 位、num2 第 0 位的权重相乘，正好对应结果从右数的那一位，也就是数组下标 i+j+1 = 2；满十的进位往左一格、放到下标 1。
14. 16把 8 加进第 2 位：它原来是 2，相加得 10。本位只能放个位 0，多出来的 1 进位到左边第 1 位（变成 1）。这一格的值就这样被更新了。
15. 171 乘 6 得 6。为什么加到第 3 位？因为 num1 第 0 位、num2 第 2 位的权重相乘，正好对应结果从右数的那一位，也就是数组下标 i+j+1 = 3；满十的进位往左一格、放到下标 2。
16. 18把 6 加进第 3 位：它原来是 4，相加得 10。本位只能放个位 0，多出来的 1 进位到左边第 2 位（变成 1）。这一格的值就这样被更新了。
17. 191 乘 5 得 5。为什么加到第 2 位？因为 num1 第 0 位、num2 第 1 位的权重相乘，正好对应结果从右数的那一位，也就是数组下标 i+j+1 = 2；满十的进位往左一格、放到下标 1。
18. 20把 5 加进第 2 位：它原来是 1，相加得 6。本位只能放个位 6，多出来的 0 进位到左边第 1 位（变成 1）。这一格的值就这样被更新了。
19. 211 乘 4 得 4。为什么加到第 1 位？因为 num1 第 0 位、num2 第 0 位的权重相乘，正好对应结果从右数的那一位，也就是数组下标 i+j+1 = 1；满十的进位往左一格、放到下标 0。
20. 22把 4 加进第 1 位：它原来是 1，相加得 5。本位只能放个位 5，多出来的 0 进位到左边第 0 位（变成 0）。这一格的值就这样被更新了。
21. 239 对数字（3×3）两两相乘、逐步进位，全部加完后草稿纸定格成 [0, 5, 6, 0, 8, 8]。因为每一步都做了「本位留个位、进位进左边」，所以现在每个格子都已经是 0~9 的单个数字了。
22. 24把格子从左到右连起来是 "056088"，最高位是 0（因为乘积没占满 6 位），去掉这个前导 0 得到最终答案 "56088"。绿框就是真正保留下来的那几位。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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"

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);
    for (int i = m - 1; i >= 0; --i)
        for (int j = n - 1; j >= 0; --j) {
            int mul = (num1[i]-'0') * (num2[j]-'0');
            int s = mul + res[i + j + 1];
            res[i + j + 1] = s % 10;
            res[i + j]    += s / 10;
        }
    string out;
    for (int d : res) if (!(out.empty() && d == 0)) out += ('0' + d);
    return out.empty() ? "0" : out;
}

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 位
    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 s = mul + res[i + j + 1];  // 加上该位已有值
            res[i + j + 1] = s % 10;       // 本位留个位
            res[i + j]    += s / 10;       // 进位进左一位
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int d : res) if (!(sb.length() == 0 && d == 0)) sb.append(d);
    return sb.length() == 0 ? "0" : sb.toString();
}

复杂度

面试官可能追问