1.题目
2.代码
介绍一种比较简单的方法,就是先将字符串逆序,然后取出其中每一位的数相乘、相加。最后再考虑进位问题。
class Solution {
public:
string multiply(string num1, string num2) {
//先排除边界情况,防止输出"00000..."
if(num1=="0"||num2=="0") return "0";
int size1=num1.size(),size2=num2.size();
vector<int> tem(size1+size2-1,0);
//先将字符串逆序
reverse(num1.begin(),num1.end());
reverse(num2.begin(),num2.end());
//无进位相加
for(int i=0;i<size1;i++){
for(int j=0;j<size2;j++){
tem[i+j]+=(num1[i]-'0')*(num2[j]-'0');
}
}
//t记录余数和进位,n防止越界。
int t=0,n=0;
string str;
//处理进位问题
while(n<size1+size2-1||t){
if(n<size1+size2-1) t+=tem[n++];
str+=t%10+'0';
t=t/10;
}
reverse(str.begin(),str.end());
return str;
}
};
3.提交结果
时间复杂度:O(n^2)。