字符串乘法
原创
题目描述
难度: 中等
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
- 示例 1: 输入: num1 = "2", num2 = "3" 输出: "6"
- 示例 2: 输入: num1 = "123", num2 = "456" 输出: "56088"
解题思路:
该算法是通过两数相乘时，乘数某位与被乘数某位相乘，与产生结果的位置的规律来完成。具体规律如下：
乘数 num1 位数为 M，被乘数 num2 位数为 N， num1 x num2 结果 res 最大总位数为 M+N
num1i x num2j 的结果为 tmp(位数为两位，"0x","xy"的形式)，其第一位位于 resi+j，第二位位于 resi+j+1。
image.png
具体实现
import (
"fmt"
"strconv"
)
func main() {
fmt.Println(multiply("999", "999"))
}
func multiply(num1 string, num2 string) string {
if num1 == "0" || num2 == "0" {
return "0"
}
m, n := len(num1), len(num2)
ret := make([]int, m+n)
for i := m - 1; i >= 0; i-- {
y := int(num1[i] - '0')
for j := n - 1; j >= 0; j-- {
x := int(num2[j] - '0')
temp := (x * y) + ret[i+j+1]
ret[i+j+1] = temp % 10
ret[i+j] += temp / 10
}
}
// 去掉前缀0
j := 0
for j < m+n && ret[j] == 0 {
j++
}
var retS string
for i := j; i < len(ret); i++ {
retS += strconv.Itoa(ret[i])
}
return retS
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录