golang刷leetcode 技巧（48）大数相乘
golang刷leetcode 技巧（48）大数相乘
golangLeetcode
发布于 2022-08-02 18:50:54
发布于 2022-08-02 18:50:54
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
解题思路：
1，两数相乘最大长度是两个数的长度相加
2，num1[i] 和 num2[j]相乘，结果只影响i+j 位和i+j+1位
r[i+j+1]+= (r[i+j]+n1[i]*n2[j])/10
r[i+j]= (r[i+j]+n1[i]*n2[j])%103，计算结果转string需要关注头部的0，如果全0，保留一个0
代码实现：
func multiply(num1 string, num2 string) string {
n1:=str2int(num1)
n2:=str2int(num2)
if n1==nil || n2==nil{
return ""
}
r:=make([]int64,len(n1)+len(n2))
for i:=0;i<len(n1);i++{
for j:=0;j<len(n2);j++{
r[i+j+1]+= (r[i+j]+n1[i]*n2[j])/10
r[i+j]= (r[i+j]+n1[i]*n2[j])%10
}
}
var s string
j:=len(r)-1
for j>0 && r[j]==0{
j--
}
for i:=0;i<=j;i++{
s=fmt.Sprintf("%d",r[i])+s
}
return s
}
func str2int(num string )[]int64{
if len(num)==0{
return nil
}
var r []int64
for i:=0;i<len(num);i++{
v,err:=strconv.ParseInt(string([]byte{num[i]}),10,10)
if err!=nil{
return nil
}
r=append([]int64{v},r...)
}
return r
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-04-18，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体分享计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读