0043.字符串相乘
给定两个以字符串形式表示的非负整数 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本身。
解题思路
- 反转字符串
- 逐位相乘，进位相加，求余
- 去除前置零
- 转为字符串
func multiply(num1 string, num2 string) string {
// 反转字符串
num1 = reverse(num1)
num2 = reverse(num2)
var products = make([]int, len(num1)+len(num2))
// 逐位相乘, 进位相加，求余
for i := 0; i < len(num1); i++ {
for j := 0; j < len(num2); j++ {
products[i+j] += int(num1[i]-'0') * int(num2[j]-'0')
// 处理进位
products[i+j+1] += products[i+j] / 10
products[i+j] = products[i+j] % 10
}
}
// 去掉前置0
for len(products) > 1 && products[len(products)-1] == 0 {
products = products[:len(products)-1]
}
// 转为字符串
var result string
for i := len(products) - 1; i >= 0; i-- {
result += fmt.Sprint(products[i])
}
return result
}
func reverse(str string) string {
var result = []rune(str)
var left, right = 0, len(result) - 1
for left < right {
result[left], result[right] = result[right], result[left]
left++
right--
}
return string(result)
}