LeetCode 43. 字符串相乘
题目描述
思路分析
竖式乘法
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func multiply(num1 string, num2 string) string {
if num1 == "0" || num2 == "0" {
return "0"
}
m, n := len(num1), len(num2)
res := make([]int, m+n)
for i := m - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
mul := int(num1[i]-'0') * int(num2[j]-'0')
sum := mul + res[i+j+1]
res[i+j+1] = sum % 10
res[i+j] += sum / 10
}
}
var sb strings.Builder
for _, digit := range res {
sb.WriteString(fmt.Sprintf("%d", digit))
}
return strings.TrimLeft(sb.String(), "0")
}
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
func multiply(num1 string, num2 string) string {
if num1 == "0" || num2 == "0" {
return "0"
}
n1, n2 := len(num1), len(num2)
res := make([]int, n1+n2)
// 从右到左遍历 num1 和 num2
for i := n1 - 1; i >= 0; i-- {
for j := n2 - 1; j >= 0; j-- {
mul := int(num1[i]-'0') * int(num2[j]-'0')
p1, p2 := i+j, i+j+1
sum := mul + res[p2]
res[p2] = sum % 10
res[p1] += sum / 10
}
}
i := 0
for i < len(res) && res[i] == 0 {
i++
}
result := ""
for ; i < len(res); i++ {
result += string(res[i] + '0')
}
return result
}
- 时间复杂度：O (m * n)，其中 m 和 n 分别是
num1和num2的长度。- 空间复杂度：O (m + n)，用于存储乘法结果数组。
1
write your code here
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！