首页 > 代码库 > leetcode第一刷_Multiply Strings
leetcode第一刷_Multiply Strings
前面提到过很多次大整数的问题,这个是真正的大整数。
我用了一个很蠢得方法,先写一个大整数和一个个位数相乘的方法,返回的结果是一个string,然后写一个string相加的方法,每次循环,用其中一个数的每一位去乘另一个数,然后加到结果上。。
多么愚蠢的思路,居然还一遍过了。。一个更好的方法是先用两个int数组把两个string存一下,每位占数组中的一个数,然后再用一个int数组保存结果,每次也是用一个数的每一位去乘另一个数,结果直接加入到结果数组的对应位置,不考虑进位,最后再统一的计算进位。这种思路非常简单,应当用我一半的代码就能写完,而且不容易出错。一般也不会溢出,因为每次乘得到的数最大是81,要相加超过INT_MAX,string得非常长才行。
下面贴我自己的代码,供大家耻笑:
void reverse(string &s){ int len = s.length(); for(int i=0;i<len/2;i++){ char t = s[i]; s[i] = s[len-i-1]; s[len-i-1] = t; } } string stringPlus(string a, string b){ int len1 = a.length(), len2 = b.length(); string res(max(len1, len2)+1, ‘0‘); int i = 0, j = 0, len = min(len1, len2), c=0; while(i<len){ int t = (a[i]-‘0‘) + (b[i]-‘0‘) + c; res[i] = t%10 + ‘0‘; c = t/10; i++; } while(i<len1){ if(c>0){ int t = (a[i]-‘0‘) + c; res[i] = t%10+‘0‘; c = t/10; }else{ res[i] = a[i]; } i++; } while(i<len2){ if(c>0){ int t = (b[i]-‘0‘) + c; res[i] = t%10+‘0‘; c = t/10; }else{ res[i] = b[i]; } i++; } return res; } string numPlus(string &a, int low, int bit){ int len = a.length(); string res(len+bit+1, ‘0‘); int start = bit, i=0, c=0; while(i<len){ int t = (a[i]-‘0‘)*low + c; res[start] = t%10+‘0‘; c = t/10; i++; start++; } if(c>0) res[start] = c+‘0‘; return res; } class Solution { public: string multiply(string num1, string num2) { if(num1 == "") return num2; if(num2 == "") return num1; string res = "0"; reverse(num1); reverse(num2); for(int i=0;i<num2.length();i++){ res = stringPlus(res, numPlus(num1, num2[i]-‘0‘, i)); } int len = res.length(); while(len-1&&res[len-1] == ‘0‘) len--; string mres(len, ‘0‘); for(int i=0;i<len;i++){ mres[i] = res[len-i-1]; } return mres; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。