[Leetcode] Multiply strings 字符串对应数字相乘

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

题意：计算字符串对应数字的乘积。参考JustDoIT的博客。

思路：先用一维向量存放计算的中间值，中间值存放对应位置乘积的和（暂不考虑进位的情况）；然后针对进位的情况，进行计算；注意要跳过开始为0的情况（因为向量开始全部初始为0）；然后将数字转化为字符串。以234*156为例：

 1 class Solution {

 public:

     string multiply(string num1, string num2)

     {

         int len1=num1.size();

         int len2=num2.size();

         vector<int> midVal(len1+len2,);

         int k=len1+len2-;

         for(int i=;i<len1;++i)

             for(int j=;j<len2;++j)

             {

                 midVal[k-i-j]+=(num1[i]-'')*(num2[j]-'');　　//从右向左

             }

         int carry=;    //进位

         for(int i=;i<len1+len2;++i)

         {

             midVal[i]+=carry;

             carry=midVal[i]/;

             midVal[i]%=;

         }

         int i=len1+len2-;

         while(midVal[i]==) //去除向量中最开始的0

             i--;

         if(i<) return ""; //全部为0时

         //将值变成字符串

         string res;

         for(;i>=;--i)

             res.push_back(midVal[i]+'');

         return res;

     }

 };

另外更高效的计算大整数乘法一般有：（1）karatsuba算法，复杂度为3n^log3≈3n^1.585，可以参考百度百科、乘法算法-Karatsuba算法。（2）基于FFT(快速傅里叶变换)的算法，复杂度为o(nlogn), 可以参考FFT, 卷积, 多项式乘法, 大整数乘法

巴特西

[Leetcode] Multiply strings 字符串对应数字相乘

最新文章

热门文章