2.字符串相加,给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。
时间: 2023-11-13 22:52:00 浏览: 125
题目描述:给定两个字符串形式表示的非负整数 num1 和 num2,返回它们的乘积,也用字符串表示。
解题思路:使用竖式乘法的方法,从低位到高位逐位相乘,将结果累加到对应的位置上。最后再将结果进行进位处理,得到最终的乘积。
具体实现可以使用两个指针分别指向 num1 和 num2 的末尾,然后从后往前逐位相乘,将结果存储在一个数组中。最后再将数组中的元素转换成字符串即可。
代码示例:
```python
class Solution:
def multiply(self, num1: str, num2: str) -> str:
m, n = len(num1), len(num2)
res = [] * (m + n)
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
mul = int(num1[i]) * int(num2[j])
p1, p2 = i + j, i + j + 1
s = mul + res[p2]
res[p1] += s // 10
res[p2] = s % 10
ans = ''.join(map(str, res)).lstrip('')
return ans if ans else ''
```
时间复杂度:O(mn),其中 m 和 n 分别为 num1 和 num2 的长度。
空间复杂度:O(m+n)。
阅读全文