注意/思路
- 保存 被乘数*[0…9]的结果备用，然后移位相加即可
- 乘数末尾是0
代码
9ms
class Solution {
public:
void ReverseStr(string& str){
int left=0, right = str.size()-1;
while(left<right){
char c = str[left];
str[left] = str[right];
str[right] = c;
left++;
right--;
}
}
void AddResult(string& result, const string& subProduct, const int shift){
int carry = 0;
while(result.size() < shift){
result += "0";
}
for(int i=shift; i<subProduct.size() + shift; i++){
if(i < result.size()){
int subSum = (result[i]-'0') + (subProduct[i-shift]-'0') + carry;
if(subSum >= 10){
subSum-= 10;
carry = 1;
} else {
carry = 0;
}
result[i] = subSum + '0';
} else {
int subSum = (subProduct[i-shift]-'0') + carry;
carry = subSum / 10;
subSum = subSum % 10;
result = result + (char)(subSum+'0');
}
}
if (carry > 0) {
result += (char)(carry + '0');
}
}
string getSubProduct(char digit, string op){
int carry = 0;
int d = digit-'0';
for(int i=0; i<op.size(); i++){
int prod = (op[i]-'0') * d + carry;
carry = prod / 10;
prod = prod % 10;
op[i] = '0' + prod;
}
if(carry > 0){
op = op + (char)(carry+'0');
}
return op;
}
string multiply(string op1, string op2) {
string result;
if(op1.empty() || op2.empty())
return result;
if(op1.size() < op2.size()){
string temp = op1;
op1 = op2;
op2 = temp;
}
string productSub[10];
ReverseStr(op1);
ReverseStr(op2);
for(int i=0; i<op2.size(); i++){
char digit = op2[i];
if(digit == '0')
continue;
if(productSub[digit-'0'].empty()){
productSub[digit-'0'] = getSubProduct(digit, op1);
}
AddResult(result, productSub[digit-'0'], i);
}
if(result.empty())
return "0";
ReverseStr(result);
return result;
}
};