LeetCode-43. 字符串相乘【数学 字符串 模拟】
- 题目描述：
- 解题思路一：模拟乘法，两个数中每一位数相乘的时候乘上他们各自的进制数，之后求和。循环时，分别记录各自的进制数
- 背诵版：
- 解题思路三：0
题目描述：
给定两个以字符串形式表示的非负整数 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本身。
解题思路一：模拟乘法，两个数中每一位数相乘的时候乘上他们各自的进制数，之后求和。循环时，分别记录各自的进制数
'123' * '456' 的求和过程就等于
=
# 3分别与6、5、4相乘，并乘上456各自的进制数1、10、100，使用for循环遍历就行了
+ 3 * 6 + 3 * 5 * 10 + 3 * 4 * 100
+ 2 * 10 * 6 + 2 * 10 * 5 * 10 + 2 * 10 * 4 * 100
+ 1 * 100 * 6 + 1 * 100 * 5 * 10 + 1 * 100 * 4 * 100求和
class Solution:def multiply(self, num1: str, num2: str) -> str:f1 = 1ans = 0# 倒序遍历for i in range(len(num1)-1,-1,-1):# 进位数f2 = 1# n1 乘以进位数n1 = int(num1[i]) * f1# 倒序遍历for j in range(len(num2)-1,-1,-1):n2 = int(num2[j]) * f2 ans += n1 * n2 # 进位数处理 *10f2 *=10f1 *=10return str(ans)
时间复杂度：O(n)
空间复杂度：O(n)
背诵版：
class Solution:def multiply(self, num1: str, num2: str) -> str:f1 = 1ans = 0for i in range(len(num1)-1,-1,-1):f2 = 1n1 = int(num1[i]) * f1for j in range(len(num2)-1,-1,-1):n2 = int(num2[j]) * f2 ans += n1 * n2 f2 *=10f1 *=10return str(ans)
时间复杂度：O(n)
空间复杂度：O(n)
解题思路三：0
时间复杂度：O(n)
空间复杂度：O(n)
♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠
