字符串相乘

[louzhedong]

题目

出处：LeetCode 算法第43题

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

1. num1 和 num2 的长度小于110。
2. num1 和 num2 只包含数字 0-9。
3. num1 和 num2 均不以零开头，除非是数字 0 本身。
4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

思路

在JS中可以使用+号使字符串变成数字，但当两个很大的数字相乘时，得到的答案会丢失精度，所以不能直接采用乘法的方式。可以通过一个字符串来存储每一位相乘得到的结果，最后再拼成最后的答案。

解答

var multiply = function (num1, num2) {
  var resultArray = [];
  for (var i = num1.length - 1; i >= 0; i--) {
    for (var j = num2.length - 1; j >= 0; j--) {
      var temp = +num1[i] * +num2[j];
      if (resultArray[i + j + 1]) {
        resultArray[i + j + 1] += temp;
      } else {
        resultArray[i + j + 1] = temp;
      }

    }
  }

  var resultLength = resultArray.length - 1;
  var carry = 0;
  for (var i = resultLength; i >= 0; i--) {
    if (!resultArray[i]) {
      resultArray[i] = 0;
    }
    resultArray[i] += carry;
    carry = Math.floor(resultArray[i] / 10);
    resultArray[i] = Number(resultArray[i] % 10);
  }
  var result = "";
  var firstZero = false;
  for (var i = 0; i <= resultLength; i++) {
    if (!firstZero && resultArray[i] == 0) {
      continue;
    } else {
      result += resultArray[i];
      firstZero = true;
    }
  }

  if (result == "") {
    return "0";
  }
  return result;
};