LeetCode 43. Multiply Strings
发布时间:2020-12-14 03:09:32 所属栏目:大数据 来源:网络整理
导读:题意 求两个字符串表示的数字相乘 思路 可能会很大,所以说使用字符串处理,模拟乘法的步骤,分解一个数的每一位和另一个数相乘,然后将得出的数加起来即可. 代码 class Solution { public : string multiply( string num1, string num2) { size_t len1 = nu
题意求两个字符串表示的数字相乘 思路可能会很大,所以说使用字符串处理,模拟乘法的步骤,分解一个数的每一位和另一个数相乘,然后将得出的数加起来即可. 代码class Solution {
public:
string multiply(string num1,string num2) {
size_t len1 = num1.length();
size_t len2 = num2.length();
if(num1 == "0" || num2 == "0"){
return "0";
}
vector<string>temp;
for(int i = 0; i < len2; i++){
temp.push_back(mul(num1,num2[i] - '0'));
}
reverse(temp.begin(),temp.end());
string ans = temp[0];
int cnt = 0;
//添加末尾0,模拟进位
for(int i = 1; i < len2;i++){
string zero = "";
for(int j = 0; j < i; j++) zero += "0";
ans = add(ans,temp[i] + zero);
}
return ans;
}
private:
//两个字符串数相加
string add(string A,string B){
int lenA = A.length();
int lenB = B.length();
string ans = "";
lenA--;lenB--;
int pos = 0;
while(lenA >= 0 && lenB >= 0){
int sum = A[lenA--] + B[lenB--] - '0' - '0' + pos;
ans += sum % 10 + '0';
pos = sum / 10;
}
while(lenA >= 0){
int sum = A[lenA--]- '0' + pos;
ans += sum % 10 + '0';
pos = sum / 10;
}
while(lenB >= 0){
int sum = B[lenB--]- '0' + pos;
ans += sum % 10 + '0';
pos = sum / 10;
}
if(pos) ans += pos + '0';
reverse(ans.begin(),ans.end());
return ans;
}
//一个字符串数和一个数相乘
string mul(string num,int val){
int len = num.length();
string ans = "";
len--;
int pos = 0;
while(len >= 0){
int mulNum = (num[len--] - '0') * val + pos;
ans += mulNum % 10 + '0';
pos = mulNum / 10;
}
if(pos) ans += pos + '0';
reverse(ans.begin(),ans.end());
return ans;
}
};
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |