[Medium]LeetCode#43. 字符串相乘
题目原地址
给定两个以字符串形式表示的非负整数 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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| func multiply(num1 string, num2 string) string {
if num1 == "0" || num2 == "0" {
return "0"
}
numMap := map[string]int{
"0": 0,
"1": 1,
"2": 2,
"3": 3,
"4": 4,
"5": 5,
"6": 6,
"7": 7,
"8": 8,
"9": 9,
}
numArr := []string{
"0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
}
res := ""
l1 := len(num1)
l2 := len(num2)
var resArr []int
n := 0
for i := l1 - 1; i >= 0; i-- {
numS := string(num1[i])
o := 0
for m := l2 - 1; m >= 0; m-- {
num2S := string(num2[m])
resV := 0
if n < len(resArr) && n+(l2-1-m) < len(resArr) {
resV = resArr[n+(l2-1-m)]
}
s := numMap[numS]*numMap[num2S] + o + resV
q := s % 10
if n+(l2-1-m) < len(resArr) {
resArr[n+(l2-1-m)] = q
} else {
resArr = append(resArr, q)
}
o = (s - q) / 10
}
if o != 0 {
resArr = append(resArr, o)
}
n++
}
for _, v := range resArr {
res = numArr[v] + res
}
return res
}
|
0ms，将每个位置上的计算结果放到对应位置的数组中,优化 给定数组长度，提前计算位置等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| func multiply(num1 string, num2 string) string {
if num1 == "0" || num2 == "0" {
return "0"
}
s:=""
alen, blen := len(num1), len(num2)
var mul, sum byte
var p1, p2 int
pos := make([]byte, alen + blen)
for i := alen - 1; i >= 0; i-- {
for j := blen - 1; j >= 0; j-- {
fmt.Println(num1[i]-'0')
mul = (num1[i] - '0') * (num2[j] - '0')
//p2当前应处理放的位数
//p1计算的下一位
p1, p2 = i + j, i + j + 1
sum = pos[p2] + mul
pos[p1] += sum / 10
pos[p2] = sum % 10
}
}
for _, v := range pos {
if !(len(s) == 0 && v == 0) {
s += string(v+'0')
}
}
return s
}
|
执拗前行