Javascript 乘以字符串

Question

我正在按照 leetcode question 做乘法

Given two non-negative integers num1 and num2 represented as strings, return the
product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to
integer directly.

Example 1:

Input: num1 = "2", num2 = "3" 
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456" 
Output: "56088"

Constraints:

- 1 <= num1.length, num2.length <= 200
- num1 and num2 consist of digits only.
- Both num1 and num2 do not contain any leading zero, except the number 0 itself.

为此使用了以下方法

1. 将字符串转为整型
2. 整数相乘

同样的算法是

const numberMap = {
    "0": 0,
    "1": 1, 
    "2": 2,
    "3": 3, 
    "4": 4,
    "5": 5,
    "6": 6,
    "7": 7, 
    "8": 8, 
    "9": 9
}
var multiply = function(num1, num2) {
    let i = num1.length
    let j = num2.length 
    let sum = currentPower = 0
    let firstNumber = secondNumber = 0
    while(i > 0 || j > 0) {
        // if I or J is equal to zero, means we have itterated hence we will set the value to one 
        const firstNum = i > 0 ? (numberMap[num1[i-1]]) * (10**currentPower) : 0
        const secondNum = j > 0 ? (numberMap[num2[j-1]]) * (10**currentPower) : 0 
        firstNumber += firstNum
        secondNumber += secondNum
        currentPower++
        i--
        j--
    }

    sum = firstNumber * secondNumber
    return sum.toString()
 }; 

但是当给出以下输入时

"123456789"
"987654321"

它产生以下输出 "121932631112635260" 而不是 "121932631112635269"

知道如何解决这个问题吗？

Answer 1

您可以将每个数字与其他数字相乘，并将索引作为位置。

Like you would do by hand, like

1  2  3  4  *  4  3  2  1
-------------------------
               1  2  3  4
            1  4  6  8
         3  6  9 12
      4  8 12 16
-------------------------
      5  3  2  2  1  1  4

此方法使用字符串的反转数组，并反转结果集。

在重新调整结果之前，数组由前导零过滤。

function multiply(a, b) {
    var aa = [...a].reverse(),
        bb = [...b].reverse(),
        p = [],
        i, j;

    for (i = 0; i < aa.length; i++) {
        for (j = 0; j < bb.length; j++) {
            if (!p[i + j]) p[i + j] = 0;
            p[i + j] += aa[i] * bb[j];
            if (p[i + j] > 9) {
                if (!p[i + j + 1]) p[i + j + 1] = 0;
                p[i + j + 1] += Math.floor(p[i + j] / 10);
                p[i + j] %= 10;
            }
        }
    }
    return p
        .reverse()
        .filter((valid => (v, i, { length }) => valid = +v || valid || i + 1 === length)(false))
        .join('');
}

console.log(multiply('2', '3'));     //     6
console.log(multiply('123', '456')); // 56088
console.log(multiply('9133', '0'));  //     0
console.log(multiply('9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999', '9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999'));