字符串相乘- [Leetcode] with JavaScript

vmjh9lq9 于 2023-02-18 发布在 Java

关注(0)|答案(3)|浏览(130)

我研究这个问题太久了，似乎找不出我的逻辑有什么问题。
提示：
给定两个表示为字符串的非负整数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
我就差一点点就找到答案了!

JavaScript

来源：https://stackoverflow.com/questions/42191421/multiply-strings-leetcode-with-javascript

3条答案

按热度按时间

roqulrg31#

您的实际结果是不准确的，因为您将结果存储在一个单一的数字类型变量中，而且中间变量 * iBase 10 * 和 * jBase 10 * 在某个点上也会变得不准确。JavaScript使用64位浮点数存储数字，因此对于大约17位或更多小数位的数字，这种表示法会失去准确性。这就是为什么您得到的是最后一位数字0而不是9。
从ECMAScript 2020开始，有了BigInt数据类型，这使得这个练习变得很简单--使用它时不会损失精度：

const multiply = (a, b) => (BigInt(a) * BigInt(b)).toString();

但是这个代码挑战是在JavaScript还没有添加BigInt支持的时候产生的，我们可以假设它的意图是在没有BigInt支持的情况下解决这个挑战。在这种情况下，你需要处理更小的数字，并保持在JavaScript可以处理的范围内。最终结果应该是一个字符串，因为一旦你把它转换成数字，错误就会出现。
下面是一个简单的实现，它模拟了您在一张纸上所做的事情：计算数字1的每一位数与数字2的每一位数的乘积，并在结果中正确的位数位置对这些乘积求和，将任何溢出值结转到下一位数：

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

一个一个二个一个一个一个三个一个一个一个一个一个四个一个
还有更聪明的算法，比如Karatsuba algorithm，它使用更少的运算来获得正确的乘积。

赞(0）回复(0）举报 2023-02-18

w7t8yxp52#

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()
};

赞(0）回复(0）举报 2023-02-18

fkaflof63#

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;
};

赞(0）回复(0）举报 2023-02-18

我来回答

字符串相乘- [Leetcode] with JavaScript

3条答案

相关问题

热门标签

最新问答