multiply-strings

题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

说明：

num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

题解

num1的第j位和num2的第i-j位相乘再求和(j从len1-1到0，i从len1+len2-2到0)，会得到ans的第i位及i-1位的进位。

string multiply(string num1, string num2) {
	if (num1 == "0" || num2 == "0")return "0";
	int len1 = num1.length();
	int len2 = num2.length();
	int i = len1 + len2 - 2;
	string res = "";
	int c = 0, x = 0;
	while (i >= 0)
	{
		x = c;//c表示上一次的进位
		for (int j = i < len1 ? i : (len1 - 1); i - j < len2 && j >= 0; j--)
			x += ((num1[j] - '0')*(num2[i - j] - '0'));
		c = x / 10;
		x = x % 10;
		res = char('0' + x) + res;
		i--;
	}
	if(c)res = char('0' + c) + res;
	return res;
}