#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;    }};*/