[[421393]]

本文轉(zhuǎn)載自微信公眾號「三分鐘學(xué)前端」，作者sisterAn。轉(zhuǎn)載本文請聯(lián)系三分鐘學(xué)前端公眾號。

給定兩個以字符串形式表示的非負(fù)整數(shù) num1 和 num2，返回 num1 和 num2 的乘積，它們的乘積也表示為字符串形式。

示例 1:

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

示例 2:

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

說明：

• num1 和 num2 的長度小于110。
• num1 和 num2 只包含數(shù)字 0-9。
• num1 和 num2 均不以零開頭，除非是數(shù)字 0 本身。
• 不能使用任何標(biāo)準(zhǔn)庫的大數(shù)類型(比如 BigInteger)或直接將輸入轉(zhuǎn)換為整數(shù)來處理。

解法一：常規(guī)解法

從右往左遍歷乘數(shù)，將乘數(shù)的每一位與被乘數(shù)相乘得到對應(yīng)的結(jié)果，再將每次得到的結(jié)果累加

另外，當(dāng)乘數(shù)的每一位與被乘數(shù)高位(非最低位)相乘的時候，注意低位補 '0'

let multiply = function(num1, num2) { 
    if (num1 === "0" || num2 === "0") return "0" 
     
    // 用于保存計算結(jié)果 
    let res = "0" 
         
    // num2 逐位與 num1 相乘 
    for (let i = num2.length - 1; i >= 0; i--) { 
        let carry = 0 
        // 保存 num2 第i位數(shù)字與 num1 相乘的結(jié)果 
        let temp = '' 
        // 補 0  
        for (let j = 0; j < num2.length - 1 - i; j++) { 
            temp+='0' 
        } 
        let n2 = num2.charAt(i) - '0' 
             
        // num2 的第 i 位數(shù)字 n2 與 num1 相乘 
        for (let j = num1.length - 1; j >= 0 || carry != 0; j--) { 
            let n1 = j < 0 ? 0 : num1.charAt(j) - '0' 
            let product = (n1 * n2 + carry) % 10 
            temp += product  
            carry = Math.floor((n1 * n2 + carry) / 10) 
        } 
        // 將當(dāng)前結(jié)果與新計算的結(jié)果求和作為新的結(jié)果 
        res = addStrings(res, Array.prototype.slice.call(temp).reverse().join("")) 
    } 
    return res 
} 
 
let addStrings = function(num1, num2) { 
    let a = num1.length, b = num2.length, result = '', tmp = 0 
    while(a || b) { 
        a ? tmp += +num1[--a] : '' 
        b ? tmp +=  +num2[--b] : '' 
         
        result = tmp % 10 + result 
        if(tmp > 9) tmp = 1 
        else tmp = 0 
    } 
    if (tmp) result = 1 + result 
    return result 
} 

復(fù)雜度分析：

• 時間復(fù)雜度：O(max(m*n , n * n))
• 空間復(fù)雜度：O(m+n)

解法二：豎式相乘(優(yōu)化)

兩個數(shù)M和N相乘的結(jié)果可以由 M 乘上 N 的每一位數(shù)的和得到 ，如下圖所示：

• 計算 num1 依次乘上 num2 的每一位的和
• 把得到的所有和按對應(yīng)的位置累加在一起，就可以得到 num1 * num2 的結(jié)果

let multiply = function(num1, num2) { 
    if(num1 === '0' || num2 === '0') return "0" 
     
    // 用于保存計算結(jié)果 
    let res = [] 
     
    // 從個位數(shù)開始逐位相乘 
    for(let i = 0 ; i < num1.length; i++){ 
        // num1 尾元素 
        let tmp1 = +num1[num1.length-1-i] 
         
        for(let j = 0; j < num2.length; j++){ 
            // num2尾元素 
            let tmp2 = +num2[num2.length-1-j] 
             
            // 判斷結(jié)果集索引位置是否有值 
            let pos = res[i+j] ? res[i+j]+tmp1*tmp2 : tmp1*tmp2 
            // 賦值給當(dāng)前索引位置 
            res[i+j] = pos%10 
            // 是否進位 這樣簡化res去除不必要的"0" 
            pos >=10 && (res[i+j+1]=res[i+j+1] ? res[i+j+1]+Math.floor(pos/10) : Math.floor(pos/10)); 
        } 
    } 
    return res.reverse().join(""); 
} 

復(fù)雜度分析：

• 時間復(fù)雜度：O(m * n)
• 空間復(fù)雜度：O(m + n)