j
jaryue
V1
2023/05/10阅读:14主题:默认主题
leetcode 43. 字符串相乘
leetcode 43. 字符串相乘
题目描述
-
字符串相乘
给定两个以字符串形式表示的非负整数 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本身。
解题思路
法1
模拟相乘:\
-
其实我们只需要进行两步操作: -
第一:将字符串转换为int数据
将每一个字符单独提取出来,减去'0'再转换为int类型就是当前的数字了
再乘以位数(个位乘1,十位*10以此类推)
依次循环求和就可以得到结果数字了
-
第二:对int数据进行乘法运算
我们可以使用加法原理,先计算第一个的数值,在第二个的时候直接用数值乘以位数再相加求和,循环的结果就是我们需要的结果
比如"1234"*"123"
-
得出1234 -
将第二个123分成100+20+3,从最后一位开始
先是r=r+3x1234(开始的r=0)
然后r=r+20x1234 最后r=r+100x1234
最后返回r就可以了
-
时间复杂度(O()) -
空间复杂度(O())
法2
乘法原理:先将两个数转换位int类型
然后直接乘就可以了
比如"1234"*"123"
-
转换1234 -
转换123 -
返回1234x123
执行结果
法1
func multiply(num1 string, num2 string) string {
if num1 == "0" || num2 == "0" {
return "0"
}
m, n := len(num1), len(num2)
pos := make([]int, m+n)
for i := m - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
mul := int((num1[i] - '0') * (num2[j] - '0'))
p1 := i + j
p2 := i + j + 1
sum := mul + pos[p2]
pos[p1] += sum / 10
pos[p2] = sum % 10
}
}
var result strings.Builder
for _, val := range pos {
if !(len(result.String()) == 0 && val == 0) {
result.WriteString(strconv.Itoa(val))
}
}
return result.String()
}
执行结果: 通过 显示详情 查看示例代码 添加备注
执行用时: 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗: 2.3 MB , 在所有 Go 提交中击败了 89.13% 的用户 通过测试用例: 311 / 311 炫耀一下:
作者介绍
j
jaryue
V1