本文主要是介绍[LeetCode]43.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.
【分析】
高精度乘法（大数乘法）
其实更多地是考察乘法运算的本质。基本思路是和加法运算有一定的相似处，都是从低位到高位对每一位进行计算。只是进位和结果长度复杂一些。
我们仍然是从低位到高位对每一位进行计算，假设第一个数长度是n，第二个数长度是m，我们知道结果长度为m+n或者m+n-1（没有进位的情况）。
对于最终结果上的某一位i，要计算这个位上的数字，我们需要对所有能组合出这一位结果的位进行乘法，即第1位和第i位，第2位和第i-1位，... ，然后累加起来，
最后我们取个位上的数值，然后剩下的作为进位放到下一轮循环中。在这里我们每一组合时都要计算有没有产生进位，如果有放到下一位上，不用所有累加起来在计算。
时间复杂度是O(m*n) 空间复杂度O(m+n)。
【代码】
/*********************************
* 日期：2015-01-28
* 作者：SJF0115
* 题目: 43.Multiply Strings
* 网址：https://oj.leetcode.com/problems/multiply-strings/
* 结果：AC
* 来源：LeetCode
* 博客：
**********************************/
#include <iostream>
#include <cstring>
using namespace std;class Solution {
public:string multiply(string num1, string num2) {int len1 = num1.length();int len2 = num2.length();// 容错处理if(len1 <= 0 || len2 <= 0){return "";}//ifint sum = 0;int len3 = len1 + len2;char result[len3];memset(result,'0',sizeof(result[0])*(len3+1));for(int i = len1 - 1,m = 0;i >= 0;--i,++m){for(int j = len2 - 1,n = 0;j >= 0;--j,++n){sum = (num1[i] - '0') * (num2[j] - '0') + result[m+n] - '0';result[m+n] = sum % 10 + '0';// 进位result[m+n+1] += sum / 10;}//for}//for//确定乘积的位数while(result[len3] == '0' && len3 > 0){--len3;}//while//注意：加'\0'result[len3+1] = '\0';//翻转int temp;for(int i = 0,j = len3;i < j;++i,--j){temp = result[i];result[i] = result[j];result[j] = temp;}//forreturn string(result);}
};int main(){Solution solution;string num1("0");string num2("123");string result = solution.multiply(num1,num2);// 输出cout<<result<<endl;return 0;
}/*for(int i = 0;i < result.size();++i){for(int j = 0;j < result[i].size();++j){cout<<result[i][j]<<" ";}cout<<endl;}*/
【分析二】
[算法]Karatsuba快速相乘算法
【代码二】
class Solution {
public:string multiply(string num1, string num2) {int len = MakeSameLen(num1,num2);if(len == 0){return 0;}//if// all digit are oneif(len == 1){return to_string((num1[0] - '0')*(num2[0] - '0'));}//ifint mid = len / 2;// Find the first half and second half of first string.string x1 = num1.substr(0,mid);string x0 = num1.substr(mid,len - mid);// Find the first half and second half of second stringstring y1 = num2.substr(0,mid);string y0 = num2.substr(mid,len - mid);// Recursively computerstring z0 = multiply(x0,y0);string z1 = multiply(AddString(x1,x0),AddString(y1,y0));string z2 = multiply(x1,y1);// (z2*10^(2*m))+((z1-z2-z0)*10^(m))+(z0)// z2*10^(2*m)string r1 = ShiftString(z2,2*(len - mid));// (z1-z2-z0)*10^(m)string r2 = ShiftString(MinusString(MinusString(z1,z2),z0),len - mid);return AddString(AddString(r1,r2),z0);}
private:// given two unequal sized bit strings, converts them to// same length by adding leading 0s in the smaller string. Returns the// the new lengthint MakeSameLen(string& num1,string& num2){int len1 = num1.length();int len2 = num2.length();if(len1 < len2){for(int i = 0;i < len2 - len1;++i){num1 = "0" + num1;}//forreturn len2;}//ifelse{for(int i = 0;i < len1 - len2;++i){num2 = "0" + num2;}//forreturn len1;}//else}// big number minus functionstring MinusString(string num1, string num2) {int len1 = num1.length();int len2 = num2.length();// 相等if(num1 == num2){return "0";}//if// 正负bool positive = true;if(len1 < len2 || (len1 == len2 && num1 < num2)){positive = false;// 交换使之num1 > num2string tmp = num1;num1 = num2;num2 = tmp;int temp = len1;len1 = len2;len2 = temp;}//ifstring result;int i = len1 - 1,j = len2 - 1;int a,b,sum,carray = 0;// 从低位到高位对位做减法while(i >= 0 || j >= 0){a = i >= 0 ? num1[i] - '0' : 0;b = j >= 0 ? num2[j] - '0' : 0;sum = a - b + carray;carray = 0;// 不够减if(sum < 0){sum += 10;carray = -1;}//ifresult.insert(result.begin(),sum + '0');--i;--j;}//while// 删除前导0string::iterator it = result.begin();while(it != result.end() && *it == '0'){++it;}//whileresult.erase(result.begin(),it);return positive ? result : "-"+result;}// big number add functionstring AddString(string num1,string num2){int len1 = num1.length();int len2 = num2.length();// 容错处理if(len1 <= 0){return num2;}//ifif(len2 <= 0){return num1;}string result;int i = len1-1,j = len2-1;int a,b,sum,carry = 0;// 倒序相加while(i >= 0 || j >= 0 || carry > 0){a = i >= 0 ? num1[i] - '0' : 0;b = j >= 0 ? num2[j] - '0' : 0;// 按位相加并加上进位sum = a + b + carry;// 进位carry = sum / 10;result.insert(result.begin(),sum % 10 + '0');--i;--j;}//whilereturn result;}// 移位string ShiftString(string num,int len){if(num == "0"){return num;}//iffor(int i = 0;i < len;++i){num += "0";}//forreturn num;}
};话说这个方法比O(n^2)快，但我实现的这个，运行时间要慢，不知如何优化？
这篇关于[LeetCode]43.Multiply Strings的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
