首页 > 程序开发 > 软件开发 > C++ >

[C++]LeetCode: 69 Multiply Strings

2015-01-06

题目: 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 Answe

题目:

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.

Answer 1: 基础法

大整数乘法

\

根据小学手算乘法的规则,我们把每一位相乘,得到一个没有进位的临时结果,如图中间的一行红色数字就是临时结果,然后把临时结果从低位起一次进位。对于一个m位整数乘以一个n位整数的结果,存储空间,最多m+n位(加上一位进位)。

Attention:

1. 如果结果中最高位为0,需要去掉前导0.

 int i = k+1;
 while(tmpres[i] == 0)i--;//去掉乘积的前导0
2. 如果结果为0,需要处理。

 if(i < 0)return "0"; //注意乘积为0的特殊情况

3. string对象的下标从0开始,最后一个字符的下标为size() - 1,下标超出范围会引起溢出错误;

即”254“ => s[0] = '2', s[1] = '5' , s[2] = '4'

4. 注意存储空间的确定,位数等。

由于用tmp[k-i-j]存储每一个临时求和结果,max(i) = len1-1; max(j) = len2-1; k取 len1&#43; len2 -2即可,k是下标,下标从零开始。

实际tmp存储空间应该是(k&#43;1) &#43; 1, 其中k&#43;1代表临时结果的数量,1代表乘法可能产生最高位的一位进位。所以

对于一个m位整数乘以一个n位整数的结果,存储空间,最多m&#43;n位。注意这个最高位对应下标为k&#43;1.

复杂度:O(N^2)

AC Code:

class Solution {
public:
&#160; &#160; string multiply(string num1, string num2) {
&#160; &#160; &#160; &#160; int len1 = num1.size();
&#160; &#160; &#160; &#160; int len2 = num2.size();
&#160; &#160; &#160; &#160; vector tmp(len1 + len2, 0);
&#160; &#160; &#160; &#160; int k = len1 + len2 - 2; //最低位即 (len1-1) * (len2-1),存储到tmp[0]
&#160; &#160; &#160; &#160;&#160;
&#160; &#160; &#160; &#160; for(int i = 0; i < len1; i++)
&#160; &#160; &#160; &#160; {
&#160; &#160; &#160; &#160; &#160; &#160; for(int j = 0; j < len2; j++)
&#160; &#160; &#160; &#160; &#160; &#160; {
&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; tmp[k-i-j] += (num1[i]-&#39;0&#39;) * (num2[j]-&#39;0&#39;);
&#160; &#160; &#160; &#160; &#160; &#160; }
&#160; &#160; &#160; &#160; }
&#160; &#160; &#160; &#160;&#160;
&#160; &#160; &#160; &#160; //处理进位
&#160; &#160; &#160; &#160; int carryBit = 0;
&#160; &#160; &#160; &#160; for(int i = 0; i < len1 + len2; i++)
&#160; &#160; &#160; &#160; {
&#160; &#160; &#160; &#160; &#160; &#160; tmp[i] += carryBit;
&#160; &#160; &#160; &#160; &#160; &#160; carryBit = tmp[i]/10;
&#160; &#160; &#160; &#160; &#160; &#160; tmp[i] %= 10;
&#160; &#160; &#160; &#160; }
&#160; &#160; &#160; &#160;&#160;
&#160; &#160; &#160; &#160; int i = k + 1;
&#160; &#160; &#160; &#160; while(tmp[i] == 0) i--; &#160;//去除乘积前导0
&#160; &#160; &#160; &#160; if(i < 0) return "0"; &#160; &#160;//处理特殊情况乘积为0
&#160; &#160; &#160; &#160;&#160;
&#160; &#160; &#160; &#160; string ret;
&#160; &#160; &#160; &#160; for(;i >= 0; i--)
&#160; &#160; &#160; &#160; {
&#160; &#160; &#160; &#160; &#160; &#160; ret.push_back(tmp[i] + &#39;0&#39;);
&#160; &#160; &#160; &#160; }
&#160; &#160; &#160; &#160;&#160;
&#160; &#160; &#160; &#160; return ret;
&#160; &#160; }
};

Answer 2: FFT方法(待仔细研究)

这道题其实还有更加优的做法,就是用十大最牛的算法之一--Fast Fourier transform(FFT)。使用FFT可以在O(nlogn)时间内求出多项式的乘法,在这里只需要把变量x带入10,然后按照求多项式的方法就可以求出两个大整数的成绩了。不过FFT实现不是很简单,所以在面试中一般不需要写代码,只需要知道这个思路和基本工作原理就可以了哈。

查阅资料,有篇博文写的比较详细:使用快速傅里叶变换计算大整数乘法

向量 {ck} 是向量 {ai} 和向量 {bj} 的卷积。根据卷积定理,向量卷积的离散傅里叶变换是向量离散傅里叶变换的乘积。于是,我们可以按照以下步骤来计算大整数乘法:

  1. 分别求出向量 {ai} 和向量 {bj} 的离散傅里叶变换 {Ai} 和 {Bj}。
  2. 将 {Ai} 和 {Bj} 逐项相乘得到向量 {Ck}。
  3. 对 {Ck} 求离散傅里叶逆变换,得到的向量 {ck} 就是向量 {ai} 和向量 {bj} 的卷积。
  4. 对的向量 {ck} 进行适当的进位就得到了大整数 a 和 b 的乘积 c。
我们根据以上思路去计算,直接进行离散傅里叶变换的计算复杂度是 O(N2)。快速傅里叶变换可以计算出与直接计算相同的结果,但只需要 O(N logN) 的计算复杂度。

快速傅里叶变换的要点如下:一个界长为 N 的离散傅里叶变换可以重新写成两个界长各为 N/2 的离散傅里叶变换之和。其中一个变换由原来 N 个点中的偶数点构成,另一个变换由奇数点构成。这个过程可以递归地进行下去,直到我们将全部数据细分为界长为 1 的变换。什么是界长为 1 的傅里叶变换呢?它正是把一个输入&#20540;复制成它的一个输出&#20540;的恒等运算。要实现以上算法,最容易的情况是原始的 N 为 2 的整幂次项,如果数据集的界长不是 2 的幂次时,则可添上一些零&#20540;,直到 2 的下一幂次。在这个算法中,每递归一次需 N 阶运算,共需要 log N 次递归,所以快速傅里叶变换算法的时间复杂度是 O(N logN)。




相关文章
最新文章
热点推荐