Leetcode 43. Multiply Strings
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1:
Input: num1 = “2”, num2 = “3”
Output: “6”
Example 2:
Input: num1 = “123”, num2 = “456”
Output: “56088”
Note:
The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
解析：
给定两个字符串表示的数字，计算两个数字的乘积，并返回结果的字符表示。
字符串格式表示可以计算超大数值相乘，不受int或long的数值范围限制。
我们都熟悉笔算的整数乘积，按照被乘数逐位与乘数求积，保存进位；当被乘数换位时，结果递增一个数量级，与先前结果求和。
此题目就是采用乘积笔算的过程。
[cc lang="C++"]
123
*
456
————————————
738
615
492
————————————
56088
[/cc]
[cc lang="C++"]
class Solution {
public:
string multiply(string num1, string num2) {
//如果有其中一个乘数的字符串表示为空，则返回空字符串
if (num1.empty() || num2.empty())
return string();
if (num1 == "0" || num2 == "0")
return "0";
//按照整数从低位到高位计算，翻转两个乘数字符串
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
//求两个乘数字符串的长度
int len1 = strlen(num1.c_str()), len2 = strlen(num2.c_str());
//定义乘法结果字符串
string ret = "";
//保存进位
int carry = 0;
for (int i = 0; i < len1; i++)
{
//乘数的处理起始位
size_t pos = i;
for (int j = 0; j < len2; j++)
{
int temp = (num1[i] - '0') * (num2[j] - '0') + carry;
//向当前位加入结果
if (pos < ret.length())
{
temp = temp + (ret[pos] - '0');
ret[pos] = temp % 10 + '0';
cout << "pos < ret.length,temp:" <
ret.append(1, carry + ‘0’);
carry = 0;
}//for
//翻转整个结果字符串
reverse(ret.begin(), ret.end());
return ret;
}
};
[/cc]
运行结果如下：
参考：
https://blog.csdn.net/fly_yr/article/details/48055617
About Author
