题目

大整数乘法

 

思路:

1. 转化成分组背包问题, 代码比较 tricky

2. 将 string 相乘转化为 string 按位乘再加的过程

3. 细节. 不同长度 string 相加可以先补 0, 对齐. 按位相乘的时候, 可以从左向右计算, 便于移位

 

代码:

class Solution {public:    string multiply(string num1, string num2) {		if(num1.size() <= 0 || num2.size() <= 0)			return "";		if(num1.size() == 1 && num1[0] == '0')			return "0";		if(num2.size() == 1 && num2[0] == '0')			return "0";		if(num1.size() < num2.size()) {			swap(num1, num2);		}		string res;		for(int i = 0; i < num2.size(); i++) {			string party = oneBitMultipy(num1, num2[i]-'0');			res.push_back('0');			res = add(res, party);		}		return res;    }	string add(string num1, string num2) {		string res = "";		int len1 = num1.size(), len2 = num2.size();		if(len1 < len2) {			res.append(num2.size()-num1.size(), '0').append(num1);			num1 = res;		}else if(len1 > len2) {			res.append(num1.size()-num2.size(), '0').append(num2);			num2 = res;		}		res.clear();		int leftover = 0, len = num1.size()-1;		int i;		for(i = 0; i < num1.size(); i ++) {			int tmp = leftover+num1[len-i]-'0'+num2[len-i]-'0';			res.push_back(tmp%10+'0');			leftover = tmp/10;		}				if(leftover) {			res.push_back('0'+leftover);		}		reverse(res.begin(), res.end());		return res;	}	string oneBitMultipy(string num1, int bit) {		string res;		int leftover = 0;		for(int i = num1.size()-1; i >= 0; i--) {			int tmp = (num1[i]-'0')*bit + leftover;			res.push_back(tmp%10+'0');			leftover = tmp/10;		}		if(leftover) {			res.push_back(leftover+'0');		}		reverse(res.begin(), res.end());		return res;	}};