leecode 解题总结：43. Multiply Strings

#include <iostream>#include <stdio.h>#include <vector>#include <sstream>#include <algorithm>using namespace std;/*问题:Given two non-negative integers num1 and num2 rePResented as strings, return the product of num1 and num2.Note:The length of both num1 and num2 is < 110.Both num1 and num2 contains only digits 0-9.Both num1 and num2 does not contain any leading zero.You must not use any built-in BigInteger library or convert the inputs to integer directly.分析:这道题目是两个字符串对应的整数相乘，这个是大整数乘法。那么接下来就要分析乘法是如何处理的。设两个乘数中位数较多的为num1,位数较少的乘数为num2，那么可以把num2的每一位分解，然后用每一位分别乘以乘数，保存计算的结果。num1 * num2的个位，记录结果R1num1 * num2的十位，记录结果R2,R2后面再添1个0...num1 * num2的n位，记录结果Rn,Rn后面添n-1个0对R1~Rn进行累加，记录进位pass，计算最终的结果之前是用一个数组来做，每个元素保留4位，然后记录进位结果120 * 75=9000	120	 75    600   840   9000输入:120 750 99133 0输出:9000810关键:1 一种简单解法：两个数相乘，乘积的位数最多为两个数的位数之和因此得到计算第i+j+1位tmp = (sum[i + j + 1] - '0') + (num1[i] - '0')*(num2[j] - '0') string sum(size1 + size2 , '0');//设定初始结果for(int i = size1 - 1 ; i >= 0 ; --i){	carry = 0;	for(int j = size2 - 1 ; j >= 0 ; j--)	{		temp = (sum[i + j + 1] - '0') + (num1.at(i) - '0') * (num2.at(j) - '0') + carry;//不要漏了进位		sum[i + j + 1] = temp % 10 + '0';//这里直接用 % . /不需要判断		carry = temp / 10;	}	//这里最后的进位要加上,这里i对应的是最高位,比如75 * 120,5对应倒数第一位，5*120=600占据3位，由于没有进位，无需占据第2位的进位	sum[i] += carry;}size_t pos = sum.find_first_not_of("0");//找到结果真正起始位置*/class Solution {public:    string multiply(string num1, string num2) {        if(num1.empty() || num2.empty())		{			return "";		}		int size1 = num1.size();		int size2 = num2.size();		int temp;		int carry = 0;		string sum(size1 + size2 , '0');//设定初始结果		for(int i = size1 - 1 ; i >= 0 ; --i)		{			carry = 0;			for(int j = size2 - 1 ; j >= 0 ; j--)			{				temp = (sum[i + j + 1] - '0') + (num1.at(i) - '0') * (num2.at(j) - '0') + carry;//不要漏了进位				sum[i + j + 1] = temp % 10 + '0';//这里直接用 % . /不需要判断				carry = temp / 10;			}			//这里最后的进位要加上,这里i对应的是最高位,比如75 * 120,5对应倒数第一位，5*120=600占据3位，由于没有进位，无需占据第2位的进位			sum[i] += carry;		}		size_t pos = sum.find_first_not_of("0");//找到结果真正起始位置		if(string::npos != pos)		{			return sum.substr(pos);		}		return "0";	}};void process(){	string num1;	string num2;	Solution solution;	while(cin >> num1 >> num2)	{		string result = solution.multiply(num1 , num2);		cout << result << endl;	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}/*class Solution2 {public:    string multiply(string num1, string num2) {        if(num1.empty() || num2.empty())		{			return "";		}		//如果乘数中有1个为0，直接输出0		if(num1 == "0" || num2 == "0")		{			return "0";		}		int len1 = num1.length();		int len2 = num2.length();		string maxNum = len1 > len2 ? num1 : num2;		string minNum = len1 > len2 ? num2 : num1;//这里易错		int maxLen = len1 > len2 ? len1 : len2;		int minLen = len1 < len2 ? len1 : len2;		vector<string> results;		string result;		int value1;		int value2;		int pass;		int digitValue;//当前位的值		//位数较少的乘数的每一位乘以另一个乘数的每一位		for(int i = minLen - 1 ; i >= 0 ; i--)		{			result = "";			value1 = minNum.at(i) - '0';			pass = 0;			stringstream stream;			//乘以的时候必须逆序，例如乘以120，必须从0开始乘			for(int j = maxLen - 1 ; j >= 0 ; j--)			{				//比如 "120" * "5" = "600"，注意这里不能直接转化为整数乘法，会导致溢出,132 * 5 = 460				value2 = maxNum.at(j) - '0';				digitValue = value1 * value2 + pass;				//需要进位				if(digitValue >= 10)				{					pass = digitValue / 10;					digitValue = digitValue % 10;				}				else				{					pass = 0;				}				stream << digitValue;//记录当前位			}			//易错，需要判断最后一次的进位是否存在，如果存在，需要继续处理			if(pass != 0)			{				stream << pass;			}			//得到的结果需要逆置			result = stream.str();			reverse(result.begin() , result.end());			//逆置完了之后，需要追加0			for(int k = 0 ; k < minLen - 1 - i; k++)			{				result += "0";			}			results.push_back(result);		}		if(results.empty())		{			return "";		}		//将得到的结果累加求和，需要计算最长的长度		int size = results.size();		pass = 0;		digitValue = 0;		maxLen = results.at( size - 1 ).length();		digitValue = 0;		stringstream resultStream;		int len;		int index;		for(int i = 0 ; i < maxLen ; i++)		{				//对每一个数的每一位进行求和,必须从最后一位进行求和			digitValue = 0;			for(int j = 0 ; j < size ; j++)			{				len = results.at(j).length();				index = len - 1 - i;				//说明当前结果已经变成0了，直接跳过				if(index < 0)				{					continue;				}				digitValue += ( results.at(j).at(index) - '0' );			}			digitValue += pass;			//判断是否需要进位			if(digitValue >= 10)			{				pass = digitValue / 10;				digitValue = digitValue % 10;			}			else			{				pass = 0;			}			resultStream << digitValue;		}		if(pass != 0)		{			resultStream << pass;		}		result = resultStream.str();		reverse(result.begin() , result.end());		return result;    }};*/