javascript - 乘以字符串

Question

问题集- 给定两个表示为字符串的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，也表示为字符串。

我的算法似乎对除了 1-9 的一个回文测试用例之外的所有测试用例都能正常工作

更新

Javascript 有一个解析方法，但我不想使用它，因为问题来自 leetcode，或者事实上来自任何此类站点，问题集明确说明了这一点。

//**Input:**
var n1 = "123456789"
var n2 = "987654321"

var multiply = function(str1, str2) {
  var sum = 0, k = 1;
  for( var i = str1.length - 1; i>=0; i--){
      var val1 = parseInt(str1[i], 10) * k;

      k *= 10;
      var d = 1;
      for(var j = str2.length - 1; j >=0; j--){
          var val2 = parseInt(str2[j], 10) * d;
          d *= 10;

          sum +=  val1 * val2;

      }
  }
  return sum.toString();
};

console.log(multiply(n1,n2))

我不明白出了什么问题。其他回文虽然工作正常。

Answer 1

此类练习的目的可能是您实现自己的大数乘法算法。当一个整数(本例中的产品)需要超过 15-16 位数字时，JavaScript 数字类型无法以足够的精度存储它，因此如果您仅对输入使用乘法运算符，结果将是错误的。

即使您在数字变量中对较小的产品求和，该总和最终也会超过 Number.MAX_SAFE_INTEGER 的限制。您需要将较小计算的结果存储在另一个数据结构中，例如数组或字符串。

这是 long multiplication algorithm 的简单实现:

function multiply(a, b) {
    const product = Array(a.length+b.length).fill(0);
    for (let i = a.length; i--; null) {
        let carry = 0;
        for (let j = b.length; j--; null) {
            product[1+i+j] += carry + a[i]*b[j];
            carry = Math.floor(product[1+i+j] / 10);
            product[1+i+j] = product[1+i+j] % 10;
        }
        product[i] += carry;
    }
    return product.join("").replace(/^0*(\d)/, "$1");
}

console.log(multiply("123456789", "987654321"));

自 ECMAScript 2020 起，JavaScript 拥有 bigint 数据类型，您可以使用它开箱即用地执行此类乘法(注意 n 后缀):

console.log((123456789n * 987654321n).toString());

注意:在浏览器中您不需要显式调用 toString()，但是上面的 Stack Snippet 控制台实现是有限的，所以它需要它。