LeetCode-43 字符串相乘

发表于 | 分类于 | 评论数： | 阅读次数：

题目：字符串相乘

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

示例 1:

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

示例 2:

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

说明：

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

思路

由于Python中的int类型是支持大数的，所以其实没有处理会不会数值过大的必要。

题目中说不允许直接转换成整数处理，其实就是希望我们实现一下乘法的过程，也就是以前学的竖式运算的过程。

1
2
3
4
5
6
7
  11
x 12
-----
  22
 11
-----
 132

思路如下：

  • 初始化结果res=0
  • 进行嵌套循环，从右边依次取num2的每个字符串num2[-j]，转换成int类型，依次与num1从右边开始逐个字符串num1[-i]相乘
  • 相乘过程中涉及到进位，可以找到规律是10 ** (i+j-2)。

实现如下：

1
2
3
4
5
6
7
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        res = 0
        for i in range(1, len(num1) + 1):
            for j in range(1, len(num2) + 1):
                res += int(num1[-i]) * int(num2[-j]) * 10 ** (i + j - 2)
        return str(res)

其他思考

如果不考虑要求，直接使用int()来转换的话，那么更简单了：

1
2
3
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        return str(int(num1) * int(num2))

运行效果与上面相比的话：

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
import time


class Solution:
    def multiply1(self, num1, num2):
        res = 0
        for i in range(1, len(num1) + 1):
            for j in range(1, len(num2) + 1):
                res += int(num1[-i]) * int(num2[-j]) * 10 ** (i + j - 2)
        return str(res)

    def multiply2(self, num1, num2):
        return str(int(num1) * int(num2))


if __name__ == '__main__':
    num1 = "1111111"
    num2 = "2222222"
    t1 = time.time()
    print(Solution().multiply1(num1, num2))
    t2 = time.time()
    print('Solution One spent {} seconds'.format(t2-t1))
    t1 = time.time()
    print(Solution().multiply2(num1, num2))
    t2 = time.time()
    print('Solution Two spent {} seconds'.format(t2 - t1))

输出如下：

1
2
3
4
2469135308642
Solution One spent 7.581710815429688e-05 seconds
2469135308642
Solution Two spent 7.152557373046875e-06 seconds

还是差了一个数量级的，再实际使用中，还是用原生的方法比较好。

如果大家有更好的方法，欢迎一起探讨。