43. 字符串相乘

[linqibin]

给定两个以字符串形式表示的非负整数 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）或直接将输入转换为整数来处理。

思路：模拟四则运算竖式。还记得大学做过一个课程设计是无限长度四则计算器。当时花了九牛二虎之力才写出来。现在做这样的题少花了很多时间，看来写程序真的不是完全吃天赋的，在智商没涨的情况下多写几年程序确实反应会更快。keep moving！

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

    const list = [];

    for(let pointer2 = num2.length - 1; pointer2 >= 0; pointer2--){        
        const temList = [];
        for(let i = pointer2; i < num2.length - 1; i++){
            temList.push(0);//先往后面补零
        }

        let borrow = 0;
        for(let pointer1 = num1.length - 1; pointer1 >= 0; pointer1--){
            let result = num1[pointer1] * num2[pointer2] + borrow;
            borrow = result >= 10 ? Math.floor(result / 10) : 0;
            temList.unshift(result%10);
        }
        if(borrow > 0) temList.unshift(borrow);
        
        if(temList[0] != 0) list.push(temList);
    }
    
    if(list.length == 1) return list[0].join("");

    let resultList = list[0];
    for(let level = 1; level < list.length; level++){
        resultList = add(resultList, list[level]);
    }

    return resultList.join("");
};

function add(numList1, numList2){

    if(numList1.length == 0) return numList2;
    if(numList2.length == 0) return numList1;
    
    let pointer1 = numList1.length - 1;
    let pointer2 = numList2.length - 1;

    let list = [];
    let borrow = 0;
    while(pointer1 >= 0 || pointer2 >= 0){
        let num1 = pointer1 >= 0? numList1[pointer1] : 0;
        let num2 = pointer2 >= 0? numList2[pointer2] : 0;
        let result = num1 + num2 + borrow;
        borrow = result >= 10 ? Math.floor(result / 10) : 0;        
        list.unshift(result%10);

        pointer1--;
        pointer2--;
    }

    if(borrow > 0) list.unshift(borrow);

    return list;
}