【LeetCode 43】字符串相乘

电玩女神 2022-12-16 06:06 159阅读 0赞

#### 题目描述 ####

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

示例 1:

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

示例 2:

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

说明：

*  num1 和 num2 的长度小于110。
 *  num1 和 num2 只包含数字 0-9。
 *  num1 和 num2 均不以零开头，除非是数字 0 本身。
 *  不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

#### 解题思路 ####

首先，对于num1和num2，如果有一个是0，那么结果就一定是0。

对于两个数的乘积，位数最多是他们两个位数的和，最少应该是比两个位数之和少1。所以，我们可以初始化一个结果数组，长度为两个数位数的和，如果最后结果的第一位是0，就直接去掉就好了。

然后，最关键的一步就是数的乘法，我们可以将每一位进行相乘，与10取余，得出的结果放在当前位，与10相除，得出的结果进到前一位。这样遍历完所有的位数，就可以实现两个字符串的相除。

时间复杂度为O(n2)

#### 代码实现 ####

/** * @param {string} num1 * @param {string} num2 * @return {string} */
    var multiply = function(num1, num2) { 
        if(num1 == "0" || num2 == "0") return "0"
        const len1 = num1.length
        const len2 = num2.length
        const res = new Array(len1 + len2).fill(0)
        
        for(let i = len1 - 1; i >= 0; i--){ 
            const n1 = num1[i]
            for(let j = len2 - 1; j >= 0; j--){ 
                const n2 = num2[j]
                const temp = n1 * n2
                const sum = res[i + j + 1] + temp
    
                res[i + j + 1] = sum % 10
                res[i + j] += sum / 10 | 0
            }
        }
        while(res[0] == 0){ 
            res.shift()
        }
        return res.join("")
    };

#### 提交结果 ####

![在这里插入图片描述][20201018222146705.png]

[20201018222146705.png]: /images/20221123/4bae7bc48e9e47e8ad6e2d5b2e29d551.png?