[leetcode] 43 Multiply Strings(模拟大数乘法)
发布时间:2020-12-14 02:14:26 所属栏目:大数据 来源:网络整理
导读:很简单的题目,模拟大数乘法。 思路:? 第一个字符串的第i位乘以第二个字符串的第j位一定是结果的第i+j位,如果i+j已经有值,直接加上去就OK,并用temp保存进位, 最后记得将结果反转,去掉前置0。这样的算法的复杂度是O(n2).利用FFT可以将算法优化到O(nl
很简单的题目,模拟大数乘法。 思路:? 第一个字符串的第i位乘以第二个字符串的第j位一定是结果的第i+j位,如果i+j已经有值,直接加上去就OK,并用temp保存进位, 最后记得将结果反转,去掉前置0。这样的算法的复杂度是O(n2).利用FFT可以将算法优化到O(nlogn),关于FFT的实现在此不再赘述,可以参考算法导论或者网上其他资料。 另外,我的博客中实现了关于大数加减乘除的详细代码,请参考我的 博客链接: http://blog.csdn.net/nk_test/article/details/48912763
class Solution { public: string multiply(string num1,string num2) { string s(1000,'0'); reverse(num1.begin(),num1.end()); reverse(num2.begin(),num2.end()); for(int i=0;i<num1.length();i++) for(int j=0;j<num2.length();j++) { int temp=(num1[i]-'0')*(num2[j]-'0'); s[i+j+1]=s[i+j+1]-'0'+(s[i+j]-'0'+temp)/10+'0'; s[i+j]=(s[i+j]-'0'+temp)%10+'0'; } reverse(s.begin(),s.end()); if(s.find_first_not_of('0')==string::npos) return "0"; else return s.substr(s.find_first_not_of('0')); } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |