乘字符串- [Leetcode]与JavaScript

Question

我研究这个问题已经太久了，我似乎找不到我的逻辑有什么问题。

迅速：

给定两个非负整数num1和num2表示为字符串，则返回num1和num2的乘积。 注意： num1和num2的长度均< 110。 num1和num2都只包含0-9位数字. num1和num2都不包含任何前导零。 不能使用任何内置的BigInteger库，也不能直接将输入转换为整数。

以下是我的尝试：

​

var multiply = function(num1, num2) {
  var result = 0;
  // if any of the nums is 0, automatically it is zero
  if (num1[0] === '0' || num2[0] === '0') {
    return '0'
  };

  var length1 = num1.length - 1;
  var length2 = num2.length - 1;
  var counterI = 0;
  var iBase10 = 1;
  for (var i = length1; i >= 0; i--) {
    iBase10 = Math.pow(10, counterI)
    counterI++;
    var counterJ = 0
    var jBase10 = 1;
    for (var j = length2; j >= 0; j--) {
      jBase10 = Math.pow(10, counterJ)
      counterJ++;
      result += (num1[i] * iBase10) * (num2[j] * jBase10)
    }
  }
  return result.toString()
};

var result = multiply("123456789", "987654321");

console.log(result); // should be 121932631112635269

​

本质上，逻辑是我可以将从字符串的右侧开始的每一个乘法添加到result到左边(到所有可能的组合，因此嵌套的for循环)。

当索引向左移动时，base10将增加到10的幂，因此每个计算都会相应地设置。

然而，当我输入以下内容时，我似乎找不到问题所在：

var result = multiply("123456789","987654321");

我得到的结果是121932631112635260，但实际答案是121932631112635269

我有点接近答案了！

Answer 1

您的实际结果是不准确的，因为您将结果存储在一个数字类型的变量中，而且中间变量iBase10和jBase10在某一点上也会变得不准确。JavaScript使用64位浮点数来存储数字，因此对于大约17位或更多小数位数的数字，这种表示就失去了准确性。这就是为什么你得到最后的0位数而不是9。

相反，您需要处理较小的数字，并保持在JavaScript所能管理的范围内。最后的结果应该是一个字符串，因为一旦您将其转换为数字，就会出现不准确的情况。

下面是一个简单的实现，它模拟了在一张纸上要做的事情:计算数字1的每一个数字的乘积和第二个数字的每一个数字，并在结果中将这些产品加到正确的数字位置，并将任何溢出都传递到下一个数字：

    123 
    456
------- *
    738      <--- intermediate products
   615
  492
------- +
  56088     <---- sum of those products

​

var multiply = function(num1, num2) {
    // Result can have at most this number of digits:
    var result = Array(num1.length + num2.length).fill(0);
    for (var j = num2.length - 1; j >= 0; j--) {
        // k is the index in the result: where to add to 
        var k = num1.length + j;
        var overflow = 0;
        for (var i = num1.length - 1; i >= 0; i--) {
            product = num2[j] * num1[i] + overflow + result[k];
            result[k] = product % 10;
            overflow = (product - result[k]) / 10;
            k--;
        }
        result[k] += overflow;
    }
    // Convert result to string, removing any prepadded zeroes
    return result.join('').replace(/^0+(.)/, '$1');
}

// I/O handling
var inputs = document.querySelectorAll('input');
var output = document.querySelector('span');

inputs[0].oninput = calculate;
inputs[1].oninput = calculate;

function calculate() {
  output.textContent = multiply(inputs[0].value, inputs[1].value);
}

input { width: 40em }

Number 1: <input><br>
Number 2: <input><br>
Product: <span></span>

​

有一些更聪明的算法，比如Karatsuba算法，它们使用较少的操作来获得正确的产品。

Answer 2

var multiply = function(num1, num2) {
let product = new Array(num1.length + num2.length).fill(0)
for (let i = num1.length; i--;) {
    let carry = 0
    for (let j = num2.length; j--;) {
        product[1 + i + j] += carry + num1[i] * num2[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");
};

或

var multiply = function(a, b) {
   return (BigInt(a)*BigInt(b)).toString()
};

Answer 3

var multiply = function(num1, num2) {
    let num1num = num1.replace('"', '');
    let num2num = num2.replace('"', '');
    let product = BigInt(num1num) * BigInt(num2num);
    let productString = product.toString();
    return productString;
};