1.
class Solution { public: string multiply(string num1, string num2) { string str; int len1=num1.size(),len2=num2.size(); for(int i=len1-1;i>=0;--i) { int n1=num1[i]-'0'; if(!n1) continue; for(int j=len2-1;j>=0;--j) { int n2=num2[j]-'0'; if(!n2) continue; string sum=to_string(n1*n2); int k=len1-1-i+len2-1-j; while(k--) sum+='0'; addstring(str,sum); } } return str.empty()?"0":str; } void addstring(string& str1,string &str2) { int k=0,i=0; reverse(str1.begin(),str1.end()); reverse(str2.begin(),str2.end()); for(i=0;i<str1.size()&&i<str2.size();++i) { int sum=str1[i]-'0'+str2[i]-'0'+k; str1[i]=sum%10+'0'; k=sum/10; } for(;i<str1.size();++i) { if(!k) break; int sum=str1[i]-'0'+k; str1[i]=sum%10+'0'; k=sum/10; } for(;i<str2.size();++i) { int sum=str2[i]-'0'+k; str1+=(sum%10+'0'); k=sum/10; } if(k) str1+='1'; reverse(str1.begin(),str1.end()); } };
2. https://leetcode.com/problems/multiply-strings/discuss/573860/C%2B%2B-easy-short-100sc-95tc
num1*num2,乘积的最长长度为num1.size()+num2.size();每两位相乘,乘积的位置在i+j+1,进的一位在i+j;num1的每一位与num2相乘过后的进位,在i处。
class Solution { public: string multiply(string num1, string num2) { if(num1=="0"||num2=="0") return "0"; string str(num1.size()+num2.size(),'0'); for(int i=num1.size()-1;i>=0;--i) { int carry=0; for(int j=num2.size()-1;j>=0;--j) { int sum=str[i+j+1]-'0'+(num1[i]-'0')*(num2[j]-'0')+carry; carry=sum/10; str[i+j+1]=sum%10+'0'; } str[i]=carry+'0'; } int pos=0; while(str[pos]=='0') {++pos;} return str.substr(pos); } };