LeetCode 43. 字符串相乘（中）

模拟竖式计算

题目

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

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

示例

示例 1:

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

示例 2: 

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

考察知识点

数组、数学

核心思想

方法一

将字符串转成数组、在把乘法结果转回字符串（不符合要求，但是，挺快的。）

方案二、模拟竖式计算

我们先来简单回顾一下小学老师教过的列竖式求乘法的过程：
如下图所示，两个数M和N相乘的结果可以由 M 乘上 N 的每一位数的和得到。
举例 123 * 456 = 123 * 6 + 123 * 50 + 123 * 400 = 738 + 6150 + 49200 = 5535

3.png

Python版本

方法一的实现

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
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        
        def str2int(_str):
            res = 0
            count = 0
            for i in range(len(_str)-1, -1, -1):
                res +=  (ord(_str[i]) - ord('0')) * 10**count
                count += 1

            return res
        
        def int2str(_int):
            res = ""
            while _int != 0:
                remainder = _int % 10
                res = str(remainder) + res
                _int //= 10

            return res
        
        
        if num1 == "0" or num2 == "0":
            return "0"

        num1 = str2int(num1)
        num2 = str2int(num2)
        res = num1 * num2
        res = int2
        str(res)

        return res

print("leet code accept!!!")
Input = ["2", "123"]
Input1 = ["3", "456"]
Answer = ["6", "56088"]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.multiply(Input[i], Input1[i])
        print(reslut==Answer[i])

时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)
执行用时 :72 ms, 在所有 Python3 提交中击败了66.27%的用户
内存消耗 :13.3 MB, 在所有 Python3 提交中击败了26.38%的用户

方法二的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):

    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        n1 = len(num1)
        n2 = len(num2)

        res = 0
        digit1 = 1
        for i in range(n1-1, -1, -1):
            digit2 = 1
            tmp = 0
            for j in range(n2-1, -1, -1):
                tmp += (int(num1[i]) *digit1) * (int(num2[j]) *digit2)
                digit2 *= 10
            res += tmp  # 完成一个竖式计算，将其与前面的结果相加。
            digit1 *= 10

        return str(res)

时间复杂度 \(O(n*m)\)，\(n\) 和 \(m\) 是两个数字的长度。
空间复杂度 \(O(1)\)
执行用时 :176 ms, 在所有 Python3 提交中击败了45.08%的用户
内存消耗 :13.5 MB, 在所有 Python3 提交中击败了26.13%的用户