字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
十进制错位相乘
思路分析
代码实现
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
| class Solution {
public:
string multiply(string num1, string num2) {
if (num1.length() < num2.length()) {
swap(num1,num2);
}
int i, j;
string strvalue = "";
vector<string> v(10);
v[0] = "";
strvalue = num2;
reverse(strvalue.begin(), strvalue.end());
v[1] = strvalue;
int forward = 0;
int value = 0;
for (i = 2; i < 10; i++) {
forward = 0;
strvalue = "";
for (j = num2.length() - 1; j >= 0; j--) {
value = (i * (num2[j] - '0') + forward);
forward = value / 10;
strvalue.insert(strvalue.begin(),value%10+'0');
}
if (forward != 0) { strvalue.insert(strvalue.begin(), forward + '0'); }
reverse(strvalue.begin(),strvalue.end());
v[i] = strvalue;
}
reverse(num1.begin(), num1.end());
string ans(num1.length() + num2.length(),'0');
for (i = 0; i < num1.length(); i++) {
strvalue = v[num1[i] - '0'];
forward = 0;
for (j = 0; j < strvalue.length(); j++) {
value = (ans[i + j] - '0' + strvalue[j] - '0') + forward;
forward = value / 10;
ans[i + j] = value % 10 + '0';
}
if (forward != 0) {
ans[i + j] = forward + '0';
}
}
while (ans.length() > 1 && ans[ans.length() - 1] == '0') {
ans.erase(ans.begin() + ans.length() - 1);
}
reverse(ans.begin(),ans.end());
return ans;
}
};
|