Medium

题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

**注意：**不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

约束条件:

  • 1 <= num1.length, num2.length <= 200
  • num1 和 num2 只包含数字
  • num1 和 num2 都不包含任何前导零，除了数字 0 本身

解题思路

解题思路

这道题要求实现大数相乘，不能直接转换为整数。主要有两种解法：

方法一：模拟竖式乘法 按照小学竖式乘法的思路，用 num2 的每一位去乘 num1，然后将结果按位相加。需要注意进位处理和位置对齐。

方法二：优化的位置映射法（推荐） 这是更优雅的解法。关键观察是：num1[i] * num2[j] 的结果应该放在结果数组的 i+j 和 i+j+1 位置。

具体步骤：

  1. 创建长度为 m+n 的结果数组，初始化为0
  2. 从右到左遍历两个字符串的每一位
  3. 计算 num1[i] * num2[j] + carry
  4. 将结果的个位数放在 pos2 = i+j+1，十位数加到 pos1 = i+j
  5. 最后将数组转换为字符串，去除前导零

这种方法的优势是逻辑清晰，不需要额外的字符串拼接操作，效率更高。

时间复杂度为O(m×n)，空间复杂度为O(m+n)，其中m、n分别是两个字符串的长度。

代码实现

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";
        
        int m = num1.length(), n = num2.length();
        vector<int> result(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 pos1 = i + j, pos2 = i + j + 1;
                int sum = mul + result[pos2];
                
                result[pos2] = sum % 10;
                result[pos1] += sum / 10;
            }
        }
        
        string res;
        for (int num : result) {
            if (!(res.empty() && num == 0)) {
                res += to_string(num);
            }
        }
        
        return res.empty() ? "0" : res;
    }
};

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        
        m, n = len(num1), len(num2)
        result = [0] * (m + n)
        
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                mul = int(num1[i]) * int(num2[j])
                pos1, pos2 = i + j, i + j + 1
                total = mul + result[pos2]
                
                result[pos2] = total % 10
                result[pos1] += total // 10
        
        # 转换为字符串并去除前导零
        start = 0
        while start < len(result) and result[start] == 0:
            start += 1
        
        return ''.join(map(str, result[start:]))

public class Solution {
    public string Multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";
        
        int m = num1.Length, n = num2.Length;
        int[] result = new int[m + n];
        
        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 pos1 = i + j, pos2 = i + j + 1;
                int sum = mul + result[pos2];
                
                result[pos2] = sum % 10;
                result[pos1] += sum / 10;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        foreach (int num in result) {
            if (!(sb.Length == 0 && num == 0)) {
                sb.Append(num);
            }
        }
        
        return sb.Length == 0 ? "0" : sb.ToString();
    }
}

var multiply = function(num1, num2) {
    if (num1 === "0" || num2 === "0") return "0";
    
    const m = num1.length;
    const n = num2.length;
    const result = new Array(m + n).fill(0);
    
    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            const mul = (num1[i] - '0') * (num2[j] - '0');
            const p1 = i + j;
            const p2 = i + j + 1;
            const sum = mul + result[p2];
            
            result[p2] = sum % 10;
            result[p1] += Math.floor(sum / 10);
        }
    }
    
    let start = 0;
    while (start < result.length && result[start] === 0) {
        start++;
    }
    
    return result.slice(start).join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n)，其中 m 和 n 分别是两个字符串的长度，需要对每对数字进行乘法运算
空间复杂度O(m + n)，需要创建长度为 m + n 的结果数组来存储中间计算结果

相关题目