字符串相乘

题目描述

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

示例：

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

分析

我们以 num1 = "123", num2 = "456"做例子

       1  2  3
       4  5  6
    --------------
    1  3  6  8
    9  1  2  0       
 4  5  6
 ------------------
 5  6  0  8  8
  • 我们循环 123，分别乘以下面的 456,
  • 3 * 456 得到的是 1368
  • 2 * 456 得到的是 912， 但此时的2应该是20， 所以得到的结果是 9120
  • 1 * 456 得到的是 456， 但此时的1应该是100，所以得到的结果是 45600
  • 将这三个结果加起来即可

注意：我们每次相乘的结果都用数组存起来， 1368 => [1,3,6,8] 如此类推

  • 后面就是大数相加了，将所有的数组都加起来，另外这里使用了分治

代码

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
    if(num1 == 0 || num2 == 0) {
        return "0";
    }

    let length1 = num1.length;
    let length2 = num2.length;

    let multiplyAdd = 0;
    let times = 0; 
    let resArr = []
    for(let i = length1 - 1; i >= 0; i--) {
        let currentNum1 = num1[i] * 1
        let resultArray = []
        for(let j = length2 - 1; j >= 0; j--) {
            const tempRes = currentNum1 * (num2[j] * 1) + multiplyAdd;
            const div = tempRes % 10;
            multiplyAdd = Math.floor(tempRes / 10);
            resultArray.unshift(div)
        }
        if(multiplyAdd > 0) {
            resultArray.unshift(multiplyAdd);
            multiplyAdd = 0;
        }
        for(let k = 0; k < times; k++) {
            resultArray.push(0)
        }
        times++;
        resArr.push(resultArray.join(""))
    }
    if(resArr.length <= 1) {
        return resArr.join("")
    }
    const test = fenzhi(resArr);

    return test.join("");

};

/** 
 * ["1386", "9120", "45600"]
 * 递归分支
 * 递归结束条件时，数组只剩下一个的时候, 直接返回
 * 剩下的就是左右两个相加了 combine(left, right),  // 简单说就是 left + right
 */ 
var fenzhi = function(arr) {
    let length = arr.length;
    if(length == 1) {
        return arr.join("");
    }

    const currentIndex = Math.floor(arr.length / 2);
    let left = arr.slice(0, currentIndex);
    let right = arr.slice(currentIndex, length);

    return  combine( fenzhi(left) , fenzhi(right) );
}

// 我这里使用大数相加
var combine = function(arr1, arr2) {
    let result = [];
    let length1 = arr1.length - 1;
    let length2 = arr2.length - 1;

    let add = 0;

    let i = 0;
    let j = 0;

    while(length1 >= 0 || length2 >= 0) {
        let num1 = length1 >= 0 ? arr1[length1] : 0;
        let num2 = length2 >= 0 ? arr2[length2] : 0
        let res = num1 * 1 + num2 * 1 + add * 1;
        let div = res % 10;
        add = Math.floor(res / 10);
        result.unshift(div);
        length2--;
        length1--;
    }
    if(add > 0) {
        result.unshift(add);
    }
    // console.log("result", result)
    return result;
}