mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 00:25:22 +08:00
66 lines
1.8 KiB
Markdown
66 lines
1.8 KiB
Markdown
# [43. Multiply Strings](https://leetcode.com/problems/multiply-strings/)
|
||
|
||
|
||
## 题目
|
||
|
||
Given two non-negative integers `num1` and `num2` represented as strings, return the product of `num1` and `num2`, also represented as a string.
|
||
|
||
**Note:** You must not use any built-in BigInteger library or convert the inputs to integer directly.
|
||
|
||
**Example 1:**
|
||
|
||
```
|
||
Input: num1 = "2", num2 = "3"
|
||
Output: "6"
|
||
```
|
||
|
||
**Example 2:**
|
||
|
||
```
|
||
Input: num1 = "123", num2 = "456"
|
||
Output: "56088"
|
||
```
|
||
|
||
**Constraints:**
|
||
|
||
- `1 <= num1.length, num2.length <= 200`
|
||
- `num1` and `num2` consist of digits only.
|
||
- Both `num1` and `num2` do not contain any leading zero, except the number `0` itself.
|
||
|
||
## 题目大意
|
||
|
||
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
|
||
|
||
## 解题思路
|
||
|
||
- 用数组模拟乘法。创建一个数组长度为 `len(num1) + len(num2)` 的数组用于存储乘积。对于任意 `0 ≤ i < len(num1)`，`0 ≤ j < len(num2)`，`num1[i] * num2[j]` 的结果位于 `tmp[i+j+1]`，如果 `tmp[i+j+1]≥10`，则将进位部分加到 `tmp[i+j]`。最后，将数组 `tmp` 转成字符串，如果最高位是 0 则舍弃最高位。
|
||
|
||
## 代码
|
||
|
||
```go
|
||
package leetcode
|
||
|
||
func multiply(num1 string, num2 string) string {
|
||
if num1 == "0" || num2 == "0" {
|
||
return "0"
|
||
}
|
||
b1, b2, tmp := []byte(num1), []byte(num2), make([]int, len(num1)+len(num2))
|
||
for i := 0; i < len(b1); i++ {
|
||
for j := 0; j < len(b2); j++ {
|
||
tmp[i+j+1] += int(b1[i]-'0') * int(b2[j]-'0')
|
||
}
|
||
}
|
||
for i := len(tmp) - 1; i > 0; i-- {
|
||
tmp[i-1] += tmp[i] / 10
|
||
tmp[i] = tmp[i] % 10
|
||
}
|
||
if tmp[0] == 0 {
|
||
tmp = tmp[1:]
|
||
}
|
||
res := make([]byte, len(tmp))
|
||
for i := 0; i < len(tmp); i++ {
|
||
res[i] = '0' + byte(tmp[i])
|
||
}
|
||
return string(res)
|
||
}
|
||
``` |