#include <iostream>#include <stdio.h>#include <vector>#include <sstream>#include <algorithm>using namespace std;/*問(wèn)題: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.分析:這道題目是兩個(gè)字符串對(duì)應(yīng)的整數(shù)相乘，這個(gè)是大整數(shù)乘法。那么接下來(lái)就要分析乘法是如何處理的。設(shè)兩個(gè)乘數(shù)中位數(shù)較多的為num1,位數(shù)較少的乘數(shù)為num2，那么可以把num2的每一位分解，然后用每一位分別乘以乘數(shù)，保存計(jì)算的結(jié)果。num1 * num2的個(gè)位，記錄結(jié)果R1num1 * num2的十位，記錄結(jié)果R2,R2后面再添1個(gè)0...num1 * num2的n位，記錄結(jié)果Rn,Rn后面添n-1個(gè)0對(duì)R1~Rn進(jìn)行累加，記錄進(jìn)位pass，計(jì)算最終的結(jié)果之前是用一個(gè)數(shù)組來(lái)做，每個(gè)元素保留4位，然后記錄進(jìn)位結(jié)果120 * 75=9000	120	 75    600   840   9000輸入:120 750 99133 0輸出:9000810關(guān)鍵:1 一種簡(jiǎn)單解法：兩個(gè)數(shù)相乘，乘積的位數(shù)最多為兩個(gè)數(shù)的位數(shù)之和因此得到計(jì)算第i+j+1位tmp = (sum[i + j + 1] - '0') + (num1[i] - '0')*(num2[j] - '0') string sum(size1 + size2 , '0');//設(shè)定初始結(jié)果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;//不要漏了進(jìn)位		sum[i + j + 1] = temp % 10 + '0';//這里直接用 % . /不需要判斷		carry = temp / 10;	}	//這里最后的進(jìn)位要加上,這里i對(duì)應(yīng)的是最高位,比如75 * 120,5對(duì)應(yīng)倒數(shù)第一位，5*120=600占據(jù)3位，由于沒(méi)有進(jìn)位，無(wú)需占據(jù)第2位的進(jìn)位	sum[i] += carry;}size_t pos = sum.find_first_not_of("0");//找到結(jié)果真正起始位置*/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');//設(shè)定初始結(jié)果		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;//不要漏了進(jìn)位				sum[i + j + 1] = temp % 10 + '0';//這里直接用 % . /不需要判斷				carry = temp / 10;			}			//這里最后的進(jìn)位要加上,這里i對(duì)應(yīng)的是最高位,比如75 * 120,5對(duì)應(yīng)倒數(shù)第一位，5*120=600占據(jù)3位，由于沒(méi)有進(jìn)位，無(wú)需占據(jù)第2位的進(jìn)位			sum[i] += carry;		}		size_t pos = sum.find_first_not_of("0");//找到結(jié)果真正起始位置		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 "";		}		//如果乘數(shù)中有1個(gè)為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;//這里易錯(cuò)		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;//當(dāng)前位的值		//位數(shù)較少的乘數(shù)的每一位乘以另一個(gè)乘數(shù)的每一位		for(int i = minLen - 1 ; i >= 0 ; i--)		{			result = "";			value1 = minNum.at(i) - '0';			pass = 0;			stringstream stream;			//乘以的時(shí)候必須逆序，例如乘以120，必須從0開(kāi)始乘			for(int j = maxLen - 1 ; j >= 0 ; j--)			{				//比如 "120" * "5" = "600"，注意這里不能直接轉(zhuǎn)化為整數(shù)乘法，會(huì)導(dǎo)致溢出,132 * 5 = 460				value2 = maxNum.at(j) - '0';				digitValue = value1 * value2 + pass;				//需要進(jìn)位				if(digitValue >= 10)				{					pass = digitValue / 10;					digitValue = digitValue % 10;				}				else				{					pass = 0;				}				stream << digitValue;//記錄當(dāng)前位			}			//易錯(cuò)，需要判斷最后一次的進(jìn)位是否存在，如果存在，需要繼續(xù)處理			if(pass != 0)			{				stream << pass;			}			//得到的結(jié)果需要逆置			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 "";		}		//將得到的結(jié)果累加求和，需要計(jì)算最長(zhǎng)的長(zhǎng)度		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++)		{				//對(duì)每一個(gè)數(shù)的每一位進(jìn)行求和,必須從最后一位進(jìn)行求和			digitValue = 0;			for(int j = 0 ; j < size ; j++)			{				len = results.at(j).length();				index = len - 1 - i;				//說(shuō)明當(dāng)前結(jié)果已經(jīng)變成0了，直接跳過(guò)				if(index < 0)				{					continue;				}				digitValue += ( results.at(j).at(index) - '0' );			}			digitValue += pass;			//判斷是否需要進(jìn)位			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;    }};*/