本文主要是介绍leetcode-43 Multiply Strings，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
开始参考discuss写了下面的程序
<span style="font-family:Microsoft YaHei;font-size:14px;">class Solution {
public:string multiply(string num1, string num2) {int len1 = num1.size(),len2 = num2.size();if(len1 == 0 || len2 == 0) return "0";//if(num1[0] == '0' || num2[0] == '0') return "0";vector<int> res(len1+len2,0);for(int i = 0; i < len1; i++){int carry = 0;int tmp1 = num1[len1-1-i] - '0';for(int j = 0; j < len2; j++){int tmp2 = num2[len2-1-j] - '0';int sum = tmp1 * tmp2 + res[i+j] + carry;carry = sum / 10;res[i+j] = sum % 10;}if(carry) res[i+len2] += carry;}int start = len1 + len2 - 1;while(res[start] == 0) start--;if(start == -1) return "0";string mulres = "";for(; start >= 0; start--){mulres += (char) (res[start]+'0');return mulres; }
};</span>
| Input: | "0", "0" |
| Output: | "" |
| Expected: | "0" |
<span style="font-family:Microsoft YaHei;font-size:14px;">//if(num1[0] == '0' || num2[0] == '0') return "0";</span>
参考：
这道题属于数值操作的题目，其实更多地是考察乘法运算的本质。基本思路是和加法运算还是近似的，只是进位和结果长度复杂一些。我们仍然是从低位到高位对每一位进行计算，假设第一个数长度是n，第二个数长度是m，我们知道结果长度为m+n或者m+n-1（没有进位的情况）。对于某一位i，要计算这个位上的数字，我们需要对所有能组合出这一位结果的位进行乘法，即第1位和第i位，第2位和第i-1位，... ，然后累加起来，最后我们取个位上的数值，然后剩下的作为进位放到下一轮循环中。这个算法两层循环，每层循环次数是O(m+n)，所以时间复杂度是O((m+n)^2)。算法中不需要额外空间，只需要维护一个进位变量即可，所以空间复杂度是O(1)。
这道题其实还有更加优的做法，就是用十大最牛的算法之一--Fast Fourier transform(FFT)。使用FFT可以在O(nlogn)时间内求出多项式的乘法，在这里只需要把变量x带入10，然后按照求多项式的方法就可以求出两个大整数的成绩了。想了解细节的朋友搜一下快速傅里叶变换求多项式乘积就可以找到相关资料了，是比较成熟的算法。不过FFT实现不是很简单，所以在面试中一般不需要写代码，只需要知道这个思路和基本工作原理就可以了哈。
http://blog.csdn.net/linhuanmars/article/details/20967763 Code_Ganker
这篇关于leetcode-43 Multiply Strings的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
