题目简介：
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
1
2
| 输入: num1 = "2", num2 = "3"
输出: "6"
|
示例 2:
1
2
| 输入: num1 = "123", num2 = "456"
输出: "56088"
|
说明：
num1 和 num2 的长度小于110。num1 和 num2 只包含数字 0-9。num1 和 num2 均不以零开头，除非是数字 0 本身。
思路：
模拟竖式乘法(小学数学的重要性2333)，用位数少的字符串去乘位数多的字符串(即位数少的摆在下面)。
然后开始以下步骤：
- 从最后一位开始，将当前一位的乘法结果加起来，得到字符串
sum。
- 根据当前的位数将
sum后补0，得到当前一位的最终结果字符串sum。
- 将
sum加到答案字符串中。
字符串相加时，可以根据 415. 字符串相加 的思路写一个函数。
tip:
- 若字符串中有
"0"字符串，直接返回"0"即可。
- 这种方法利于理解，但是时间与空间复杂度还是挺高的。
代码如下：
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| class Solution {
public:
string add_string(string &res, string& temp){
int flag = 0;
string ans;
while(res.size() < temp.size())
res = '0' + res;
while(temp.size() < res.size())
temp = '0' + temp;
for(int i = res.size() - 1; i >= 0; i--){
int sum = res[i] - '0' + temp[i] - '0';
if(flag == 1){
sum++;
flag = 0;
}
if(sum >= 10){
flag = 1;
sum -= 10;
}
ans = to_string(sum) + ans;
}
if(flag == 1)
ans = '1' + ans;
return ans;
}
string multiply(string num1, string num2) {
string res;
if(num1 == "0" || num2 == "0")
return "0";
if(num1.size() > num2.size()){
string temp = num1;
num1 = num2;
num2 = temp;
}
for(int i = num1.size() - 1; i >= 0; i--){
string sum;
int count = 0;
for(int j = num2.size() - 1; j >= 0; j--){
int now_mul = (num1[i] - '0') * (num2[j] - '0');
if(count > 0){
now_mul += count;
count = 0;
}
if(now_mul >= 10){
count = now_mul / 10;
now_mul = now_mul % 10;
}
sum = to_string(now_mul) + sum;
}
if(count > 0)
sum = to_string(count) + sum;
for(int k = 0; k < num1.size() - i - 1; k++){
sum = sum + '0';
}
res = add_string(res, sum);
}
return res;
}
};
|
