最开始的想法就是对竖式乘法的过程进行模拟（全都用 []byte 的形式），就有了如下解法（代码还是写的太少，写这点东西就花了好久），具体思路是先用每一位去做乘法，然后用算数加法加起来。
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
| func multiply(num1 string, num2 string) string {
switch {
case num1=="0" || num2=="0":
return "0"
case num1=="1":
return num2
case num2=="1":
return num1
}
retLen:=len(num1)+len(num2)
ret:=make([]byte,retLen,retLen)
var carryMul byte=0
var carryAdd byte=0
align:=0
res:=[]byte{}
for i:=len(num1)-1;i>=0;i--{
res=[]byte{}
for j:=len(num2)-1;j>=0;j--{
mul:=(num1[i]-48)*(num2[j]-48)
t:=mul%10+carryMul
carryMul=mul/10
res=append(res,t+48)
if j==0 && carryMul!=0 {
res=append(res,carryMul+48)
}
}
carryMul=0
for k:=0;k<len(res);k++ {
if ret[align+k]==0 {
ret[align+k]=48
}
add:=ret[align+k]-48+res[k]-48+carryAdd
carryAdd=add/10
ret[align+k]=add%10+48
if k==len(res)-1 && carryAdd!=0 {
ret[align+k+1]=carryAdd+48
}
}
carryAdd=0
align++
}
if ret[len(ret)-1]==0 {
ret=ret[:len(ret)-1]
}
for i:=0;i<len(ret)/2;i++ {
ret[i],ret[len(ret)-1-i]=ret[len(ret)-1-i],ret[i]
}
return string(ret)
}
|
看了一下别人的解法，发现他们找到了更好的规律。（而我可能用了最傻的方法）
参考了这个 Discuss
他们说出了竖式运算有一个规律——num1[i]*num2[j]的和的位置位于res[i+j]和res[i+j+1] 上，其中res[i+j]是取余的结果，res[i+j+1]是进位的结果。
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
| func multiply(num1 string, num2 string) string {
switch {
case num1=="0" || num2=="0":
return "0"
case num1=="1":
return num2
case num2=="1":
return num1
}
ret:=make([]byte,len(num1)+len(num2))
for i:=len(num1)-1;i>=0;i-- {
for j:=len(num2)-1;j>=0;j-- {
mul:=(num1[i]-48)*(num2[j]-48)
if ret[i+j]==0 {
ret[i+j]=48
}
if ret[i+j+1]==0 {
ret[i+j+1]=48
}
sum:=mul+ret[i+j+1]-48
ret[i+j]+=sum/10
ret[i+j+1]=sum%10+48
}
}
if ret[0]==48{
ret=ret[1:]
}
return string(ret)
}
|