Multiply Strings (大数相乘)

Multiply Strings

Multiply Strings 译作字符串相乘，取自 LeetCode 算法训练第 43 题（Multiply Strings），它还有个更加直白的称呼，叫做“大数相乘”。

此题的背景是因为计算机编程语言对于数字实现的进度缺陷和不足进而衍生出来的一道算法题，众所周知，JavaScript 的数字实现是基于 IEEE754 数值标准。在此标准下，会出现以下几种情况

0.1 + 0.2 === 0.3 // false 原因是 0.1 + 0.2 = 0.30000000000000004

0.0000003 // 3e-7

以上是对于浮点数而言，原因是 JavaScript 的数值标准只能最高显示 17 位的浮点精度。对于整数，依旧有这个问题，整数的显示进度是 10^20

1000 * 10000000000000000 * 10 = 100000000000000000000 // 20个0
1000 * 10000000000000000 * 100 = 1e+21

数值范围

以上讲的大概是精度问题，对于数值范围也是会影响到运算，JavaScript 并不能保存所有的数值，他有几个属性，表示数值范围。

Number.MIN_VALUE 能保存的最小数值，在大多数的浏览器里面是 5e-324
Number.MAX_VALUE 能保存的最大数值，在大多数的浏览器里面是 1.7976931348623157e+308

任何超出范围的数值，都会被转化为 Infinity 和 -Infinity

当然，ES6 还新增了两个基本数值范围

Number.MAX_SAFE_INTEGER 值是 9007199254740991
Number.MIN_SAFE_INTEGER 值是-9007199254740991

顾名思义，安全整数范围。

大数相乘

假设我们有两个很大数字（整数，简单一点，不考虑小数点）相乘，例如 224524532453453 * 345345345345324534534，在 js 中很明显，会得到指数型的结果 7.753850219863525e+34，但是我们需要得到正确的结果（77538502198635252387237634246045902）该怎么办？

思考一下乘法定律，例如 55 _ 68 = (50 + 5) _ (60 + 8) = (5 _ 10 + 5) _ (6 * 10 + 8)
接着思考一下小学时候我们学过的竖式运算

竖式运算

我们可以得到以下的普适方法：

申请一个数组，长度是两个数的长度减 1(为什么减 1？等等会说)
两层 for 循环(或 while)，然后每个数字对应的每个位上两两相乘，然后填入对应索引值相加的数组位中
从右向左循环，缝 10 进位，累加结果

~~似乎跳跃有点大~~，我们在说一个简单通俗一点的方法。

申请一个空数组用来缓存中间结果
2 层循环右端对齐，使两两对应位数字相乘，然后把结果unshift（push也可以）进空数组中
使用reduce(push 对应使用reduceRight),进行累加，每一次累加，把结果的个位取出，同时保留其他位，并降位 1，进入下一轮
将每一轮的结果都放在上一轮的前面，即可得出结果

接下来我们用代码实现上面的过程(仅完成第一种方法，第二种方法时间复杂度过高，变成了 O(n^3)，仅仅适用于理解，个人实测解题时间基本在 2000ms 以上（311 个实例）)

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
  if (num1 === '0' || num2 === '0') return '0' // 处理边界情况
  var l1 = num1.length,
    l2 = num2.length
  var list = new Array(l1 + l2 - 1).fill(0) // 缓存中间结果

  // 两两相乘
  for (let i = 0; i < l1; i++) {
    for (let j = 0; j < l2; j++) {
      list[i + j] += num1[i] * num2[j]
    }
  }

  var t = 0,
    r = '' // 累加

  var k = list.length // 之前说的为什么要数组长度减1的目的就在这里，可以减少一次循环

  while (k--) {
    t += list[k]
    r = (t % 10) + r // 当前位的准确结果
    t = (t / 10) | 0 // 前面几位，进位值
  }

  return t > 0 ? t + r : r
}

上述方法是常规方法，也是 LeetCode 主推的方法，此方法的运算时间应该是最快的。具体得看 LeetCode，正常会在 120ms 以内。

算法还是靠多谢多练。要悟才行。。贴一张我解答此题的提交记录

提交记录

错了并不可怕，慢慢悟就行了。急不得，熟能生巧~