题目描述
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
Example1:
输入: num1 = "2", num2 = "3" 输出: "6"
Example2:
输入: num1 = "123", num2 = "456" 输出: "56088"
说明
- num1 和 num2 的长度小于110。
- num1 和 num2 只包含数字 0-9。
- num1 和 num2 均不以零开头，除非是数字 0 本身。
- 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
解题思路
- 参考
- n位数*m位数，最大结果不超过 n + m
- 最小结果不小于 n + m - 1
- 模拟乘法
- 将所有数据不进位直接存入数组，最后统一进位即可。
class Solution {
public:
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0"){
return "0";
}
// n * m 位数，最多不超过n + m，最少不少于 n + m - 1
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
int s1 = num1.size();
int s2 = num2.size();
int ans[s1 + s2];
memset(ans, 0, sizeof(int) * (s1 + s2));
for(int i = 0; i < s1; i++){
for(int j = 0; j < s2; j++){
ans[i + j] += (num1[i] - '0') * (num2[j] - '0');
}
}
for(int i = 0; i < s1 + s2; i++){
if(ans[i] > 9){
int t = ans[i];
ans[i] = t % 10;
ans[i + 1] += t / 10;
}
}
int pos = (ans[s1 + s2 - 1] == 0 ? s1 + s2 - 2 : s1 + s2 -1);
string res;
for(; pos >=0; pos--){
res += ans[pos] + '0';
}
return res;
}
};
