「每日LeetCode」2022年12月7日

本文最后更新于：2023年3月19日 晚上

43.字符串相乘

43.字符串相乘

Category Difficulty Likes Dislikes
algorithms Medium (44.82%) 1011 -

Tags
Companies
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:
输入: num1 = “2”, num2 = “3” 输出: “6”
示例 2:
输入: num1 = “123”, num2 = “456” 输出: “56088”

提示：

  • 1 <= num1.length, num2.length <= 200
  • num1 和 num2 只能由数字组成。
  • num1 和 num2 都不包含任何前导零，除了数字 0 本身。

Discussion | Solution

思路

这段代码定义了一个名为 multiply 的函数，它接收两个字符串类型的数字 num1 和 num2，并返回它们的乘积作为一个字符串。首先，它处理了输入数字中一个或两个都是负数的情况，如果需要，将结果的符号反转。然后它定义了一个名为 sum 的内部函数，该函数接收两个字符串类型的数字 a 和 b，并返回它们的和作为一个字符串。然后它定义另一个名为 multi 的内部函数，该函数接收一个字符串类型的长数字和一个字符串类型的短数字，并返回两个数字的乘积作为字符串。然后，它找到两个输入数字中较长和较短的数字，并使用 multi 函数将短数字与长数字的每一位相乘，并使用 sum 函数将所有的乘积相加。最后，它将最终结果作为字符串返回，如果需要，带有负号。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/*
 * @lc app=leetcode.cn id=43 lang=javascript
 *
 * [43] 字符串相乘
 */

// @lc code=start
/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function (num1, num2) {
  let flag = false;
  if (num1[0] === "-" && num2[0] === "-") {
    num1 = num1.slice(1);
    num2 = num2.slice(1);
  } else if (num1[0] === "-" && num2[0] !== "-") {
    num1 = num1.slice(1);
    flag = true;
  } else if (num1[0] !== "-" && num2[0] === "-") {
    num2 = num2.slice(1);
    flag = true;
  }

  const sum = (a, b) => {
    let res = "";
    let flag = false,
      i;
    for (i = 0; i < a.length || i < b.length; i++) {
      const num1 = +(a[a.length - 1 - i] ? a[a.length - 1 - i] : 0),
        num2 = +(b[b.length - 1 - i] ? b[b.length - 1 - i] : 0);
      const sum = num1 + num2 + (flag ? 1 : 0);
      if (sum >= 10) {
        res = (sum % 10) + res;
        flag = true;
      } else {
        res = sum + res;
        flag = false;
      }
    }

    res = flag ? "1" + res : res;

    while (res[0] === "0") {
      res = res.slice(1);
    }

    return res.length === 0 ? "0" : res;
  };

  const multi = (long, short) => {
    let res = "";
    short = +short;
    let prev = 0;
    for (let i = 0; i < long.length; i++) {
      const num = long[long.length - 1 - i];
      const cur = +num;
      const numMulti = cur * short + prev;
      prev = Math.floor(numMulti / 10);
      res = (numMulti % 10) + res;
    }
    res = prev === 0 ? res : prev + res;
    while (res[0] === "0") {
      res = res.slice(1);
    }
    return res.length === 0 ? "0" : res;
  };

  const long = num1.length > num2.length ? num1 : num2,
    short = num1.length > num2.length ? num2 : num1;

  let res = "0";

  for (let i = 0; i < short.length; i++) {
    const num = short[short.length - 1 - i];
    const numMulti = multi(long, num);
    res = sum(numMulti + new Array(i).fill("0").join(""), res);
  }

  return flag ? "-" + res : res;
};
// @lc code=end