字符串相乘 - [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 的每个数字与数字 2 的每个数字的乘积，并将这些乘积在结果中的正确数字位置相加，携带在任何溢出到下一个数字：

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

    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 }

有更智能的算法，比如Karatsuba 算法，它使用更少的操作来获得正确的产品。