130 - 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）或直接将输入转换为整数来处理。

解答

第一想法就是转换，然后第四条说不行哈哈😂

看到了一个巨强的解法：

https://leetcode.com/problems/multiply-strings/discuss/17605/Easiest-JAVA-Solution-with-Graph-Explanation

之前的想法是，按照数学上的乘法来计算。但完全可以一个个相乘的值再一个个相加

Multiplication

var multiply = function(num1, num2) {
  if (num1 === "0" || num2 === "0") {
    return "0"
  }
  let pos = new Array(num1.length + num2.length)
  for (let i = 0; i < num1.length + num2.length; i++) {
    pos[i] = 0
  }
  for (let i = num1.length - 1; i >= 0; i--) {
    for (let j = num2.length - 1; j >= 0; j--) {
      const mul = parseInt(num1[i]) * parseInt(num2[j])
      const p1 = i + j
      p2 = i + j + 1
      const sum = mul + pos[p2]
      pos[p1] += ~~(sum / 10)
      pos[p2] = sum % 10
    }
  }
  if (pos[0] === 0) {
    pos.shift()
  }
  return pos.join("")
};

Runtime: 68 ms, faster than 82.58% of JavaScript online submissions for Multiply Strings.

Memory Usage: 35.8 MB, less than 25.00% of JavaScript online submissions for Multiply Strings.

func multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {
        return "0"
    }
    pos := make([]int, len(num1)+len(num2))
    for i := len(num1) - 1; i >= 0; i-- {
        for j := len(num2) - 1; j >= 0; j-- {
            mul := (num1[i] - 48) * (num2[j] - 48)
            p1 := i + j
            p2 := i + j + 1
            sum := int(mul) + pos[p2]
            pos[p1] += sum / 10
            pos[p2] = sum % 10
        }
    }
    if pos[0] == 0 {
        pos = pos[1:]
    }
    var res string
    for i := 0; i < len(pos); i++ {
        res += strconv.Itoa(pos[i])
    }
    return res
}

Runtime: 4 ms, faster than 54.02% of Go online submissions for Multiply Strings.

Memory Usage: 3 MB, less than 100.00% of Go online submissions for Multiply Strings.

    class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        pos = [0]*(len(num1)+len(num2))
        for i in range(len(num1)-1, -1, -1):
            for j in range(len(num2)-1, -1, -1):
                mul = int(num1[i])*int(num2[j])
                p1 = i+j
                p2 = i+j+1
                _sum = mul+pos[p2]
                pos[p1] += _sum//10
                pos[p2] = _sum % 10
        if pos[0] == 0:
            pos.pop(0)
        return "".join([str(x) for x in pos])

Runtime: 168 ms, faster than 33.79% of Python3 online submissions for Multiply Strings.

Memory Usage: 13.7 MB, less than 7.14% of Python3 online submissions for Multiply Strings.