乘以字符串

Question

问题集- 给定两个表示为字符串的非负整数 num1 和 num2，return 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

使用 Chrome，您可以使用任意（适用通常的免责声明）大整数的 BigInt 算法。运行这个例子可以看出它确实有所作为。

let p1 = BigInt(1000000000) * BigInt(123456789) + BigInt(123456789)
  , p2 = BigInt(1000000000) * BigInt(987654321) + BigInt(987654321)
  ;
  
console.log(`standard: =${123456789 * 987654321}`);
console.log(`standard large: =${123456789123456789 * 987654321987654321}`);
console.log(`BigInt: =${p1 * p2}`);

Answer 2

这种练习的目的可能是您实现自己的大数乘法算法。当一个整数（本例中的乘积）需要超过 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)/, "");
}

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

乘以字符串

Multiply strings

javascript

algorithm

multiplication