每天一道leetcode(Day 48)

43. 字符串相乘

题目描述

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

示例

• 示例 1:

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

• 示例  2:

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

说明：

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

解题思路

• 优化竖式相乘法

  该算法是通过两数相乘时，乘数某位与被乘数某位相乘，与产生结果的位置的规律来完成。具体规律如下：

  • 乘数 num1 位数为 len1，被乘数 num2 位数为 len2， num1 x num2 结果 res 最大总位数为 len1 + len2

  • num1[i] x num2[j] 的结果为 mul(位数为两位，”0x”,”xy”的形式)，其第一位位于 res[i+j]，第二位位于 res[i+j+1]。

  如下图所示更容易理解：
  

代码

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function (num1, num2) {
  if (num1 === "0" || num2 === "0") return "0";
  let len1 = num1.length,
    len2 = num2.length,
    res = new Array(len1 + len2).fill(0);
  // 结果最多为 m + n 位数
  for (let i = len1 - 1; i >= 0; i--) {
    for (let j = len2 - 1; j >= 0; j--) {
      // 从个位数开始，逐步相乘
      const mul = num1[i] * num2[j];
      // 乘积在结果数组中对应的位置
      const p1 = i + j,
        p2 = i + j + 1;
      // 对结果进行累加
      const sum = mul + res[p2];
      // p1-乘积十位上的数，p2-乘积个位上的数
      // 加上上一次进位的数
      res[p1] += Math.floor(sum / 10);
      res[p2] = sum % 10;
    }
  }
  if (res[0] === 0) res.shift();
  return res.join("");
};

参考

43. 字符串相乘