题目链接
tag:
- Medium；
question：
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1:
Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:
Input: num1 = "123", num2 = "456"
Output: "56088"
Note:
- The length of both num1 and num2 is < 110.
- Both num1 and num2 contain only digits 0-9.
- Both num1 and num2 do not contain any leading zero, except the number 0 itself.
- You must not use any built-in BigInteger library or convert the inputs to integer directly.
思路：
字符串相乘，主要应该是为了解决大数相乘的问题。基本数据类型无法胜任大数计算，除非像java有BigInteger这种专门的大数的数据类型，那么最好的方法就是将数字转换成字符串再计算，这样就不存在数据溢出的问题了。
既然归根到底都是乘法计算，虽然转换成了字符串，当然也要遵循乘法运算规则，两个多位数的乘法过程，都是每位相乘，然后错位相加，然后把错位相加后的结果保存到一个一维数组中，然后分别每位上算进位，最后每个数字都变成一位，然后要做的是去除掉首位0，最后把每位上的数字按顺序保存到结果中即可。
下面，我们以289*758为例
- 首先我们把每一位相乘，得到一个没有进位的临时结果，如图中中间的一行红色数字就是临时结果。
- 然后把临时结果从低位起依次进位。
- 对于一个m位整数乘以n位整数的结果，最多只有m+n位。
class Solution {
public:
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0" || num1.empty() || num2.empty())
return "0";
string res = "";
int size1 = num1.size(), size2 = num2.size();
vector<int> vals(size1 + size2);
for (int i=size1-1; i>=0; --i) {
for (int j=size2-1; j>=0; --j) {
int mul = (num1[i] - '0') * (num2[j] - '0');
int p1 = i + j;
int p2 = i + j + 1;
int sum = mul + vals[p2];
vals[p1] += sum / 10;
vals[p2] = sum % 10;
}
}
for (int val : vals) {
if (!res.empty() || val != 0) res.push_back(val + '0');
}
return res.empty() ? "0" : res;
}
};
