Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
in.txt
solve.cpp

README.md

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.

Solution

模拟法

根据乘法规则,乘数逐位与被乘数相乘,然后相加,因此先实现乘数只有一位的情况:

为了防止进位处理,把结果reverse保存,即高位在后面,地位在前面,然后被乘数和乘数逐一相乘,如果大于10,则需要进位:

string multiply(string num1, int i) {
	if (i == 0)
		return "0";
	if (i == 1) {
		reverse(begin(num1), end(num1)); // 返回结果总是reverse的
		return num1;
	}
	string result;
	int n = num1.size();
	int j = n - 1;
	int carry = 0;
	for (int j = n - 1; j >= 0; --j) {
		int c = (num1[j] - '0') * i + carry;
		carry = c / 10;
		c %= 10;
		result.push_back(c + '0');
	}
	if (carry != 0)
		result.push_back(carry + '0');
	//reverse(begin(result), end(result));
	return result;
}

算得每个结果后,需要把所有的相乘结果相加,因此需要实现大数加法:

/**
注意num1 和 num2都是reverse的,并且结果也是reverse的
*/
string add(string num1, string num2) {
	string result;
	int i = 0, j = 0;
	int carry = 0;
	while (i < num1.size() && j < num1.size()) {
		int a = num1[i] - '0';
		int b = num2[j] - '0';
		int c = a + b + carry;
		carry = c / 10;
		c %= 10;
		result.push_back(c + '0');
		i++, j++;
	}
	while (i < num1.size()) {
		int c = num1[i] - '0' + carry;
		carry = c / 10;
		c %= 10;
		result.push_back(c + '0');
		i++;
	}
	while (j < num2.size()) {

		int c = num2[j] - '0' + carry;
		carry = c / 10;
		c %= 10;
		result.push_back(c + '0');
		j++;
	}
	if (carry != 0) {
		result.push_back(carry + '0');
	}
	return result;
}

最后结果就是乘数逐位与被乘数相乘即可,注意乘数不是各位时,应该乘以10^n,n位第几位:

string multiply(string num1, string num2) {
	if (  num1 == "0" || num1 == ""
	   || num2 == "0" || num2 == "") {
		return "0";
	}
	/*
	 * 反而更慢? 
	if (num1.size() < num2.size())
		return multiply(num2, num1);
	*/
	string result;
	int n = num2.size();
	for (int i = n - 1; i >= 0; --i) {
		if (num2[i] == '0')
			continue;
		string s = multiply(num1, num2[i] - '0');
		string zeros;
		for (int j = 1; j < n - i; ++j)
			zeros.push_back('0');
		s = zeros + s;
		result = add(result, s);
	}
	reverse(begin(result), end(result));
	return result == "" ? "0" : result;
}
You can’t perform that action at this time.