LeetCode题解——Multiply Strings

本文主要是介绍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.

此题可以用来求两个大数相乘。

思路：逐位相乘处理进位法。

假设两个字符串a和b以及保存结果的字符串c. 对每个i，j;将a[i]*b[j]的结果加上c[i+j+1]上，所以c[i+j+1]是所有i+j位的乘积的累加。得到每位的结果后，在进行进位处理。最后再去掉c前面的'0'，得到的结果即为最终结果。

乘积是逐位相乘，也就是ai*bj，结果加入到积C的第i+j+1位，最后处理进位即可，例如：A =17 = 1*10 + 7 = （1,7）最后是十进制的幂表示法，幂次是从高位到低位，以下同。B=25 = 2*10 + 5 = (2, 5);C = A * B = ( 0,1 * 2, 1 * 5 + 2 * 7,7 * 5) = (0,2,19,35) = (0,2,22,5) = (0,4,2,5)=(4,2,5)。

class Solution {
public:string multiply(string num1, string num2) {if(!num1.size() || !num2.size()) return NULL;int N1 = num1.size(), N2 = num2.size();vector<int> ans(N1+N2,0);//逐位运算for(int i=0; i<N1; i++){for(int j=0; j<N2; j++){ans[i+j+1] += (num1[i]-'0')*(num2[j]-'0');}}// 处理进位for(int i = ans.size()-1; i>=0; i--){if(ans[i]>=10){ans[i-1] += ans[i]/10;ans[i] %= 10;}}//去掉多余的0int i =0 ;while(ans[i]==0 && i<ans.size()-1) i++;string s(ans.size()-i,'0');for(int j=0;i<ans.size();i++,j++){s[j]='0'+ans[i];}return s;}
};

这篇关于LeetCode题解——Multiply Strings的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---