个人主页:Lei宝啊
愿所有美好如期而遇
题目链接如下:
题目
思路
我们首先不能将字符串全部转换为数字,因为存储不下,而且注意也不允许,所以我们应该想到用一个字符串尾部的单位乘一个字符串,然后存储得到的字符串,再由尾部的倒数第二位乘,再存储结果字符串,并且根据位数在结果字符串后补0,最终得到的所有结果字符串相加,就是我们的答案。
字符串相加:(C++)字符串相加
图解
代码
string multiply(string num1, string num2) { if(num1 == "0" || num2 == "0") { return "0"; } int s1 = num1.size(); int s2 = num2.size(); if(s1 > s2) { num1.swap(num2); s1 = num1.size(); s2 = num2.size(); } int count = 0; string s[201]; for(int i=s1-1; i>=0; i--) { int ch1 = num1[i] - 48; int add = 0; for(int j=s2-1; j>=0; j--) { int ch2 = num2[j] - 48; s[i] += ch2 * ch1 % 10 + 48 + add; add = ch2 * ch1 / 10; } if(add > 0) { s[i] += add + 48; } reverse(s[i].begin(),s[i].end()); for(int k=0; k<count; k++) { s[i] += '0'; } count++; } string result; for(int i=0; i<s1; i++) { result = addStrings(result,s[i]); } return result; }
string addStrings(string num1, string num2) { string result; int next = 0; char tmp1 = 0; char tmp2 = 0; while(!num1.empty() || !num2.empty()) { if(!num1.empty()) tmp1 = num1[num1.size()-1] - 48; else tmp1 = 0; if(!num2.empty()) tmp2 = num2[num2.size()-1] - 48; else tmp2 = 0; int sum = tmp1 + tmp2 + next; next = sum / 10; sum %= 10; result += (sum+48); if(!num1.empty()) num1.erase(num1.end()-1); if(!num2.empty()) num2.erase(num2.end()-1); } if(next > 0) result += '1'; reverse(result.begin(),result.end()); return result; }