给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
题目描述
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
思路
通过观察,m位数 * n位数的结果最多是 (m + n)位,并且由于int类型数据的局限性,不能用普通乘法得到相应的结果,
所以可以考虑构建一个(m + n)位的string数组保存num1 和num2 每一位相乘的结果,并且考虑进位。
实现
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
string multiply(string num1, string num2)
{
string str1 = "0";
if (num1.compare("0") == 0 || num2.compare("0") == 0)
{
}
else
{
int n = num1.size();
int m = num2.size();
vector<int> num(m + n);
for (int i = m - 1; i >= 0; i--)
{
for (int j = n - 1; j >= 0; j--)
{
int temp = (num1[j] - '0') * (num2[i] - '0');
num[i + j + 1] += temp;
}
}
//最后一位不需要进位,所以从倒数第二位开始
for (int i = m + n - 2; i >= 0; i--)
{
num[i] += num[i + 1] / 10;
num[i + 1] = num[i + 1] % 10;
}
if (num[0] == 0)
{
num.erase(num.begin());
}
stringstream ss;
copy(num.begin(), num.end(), ostream_iterator<int>(ss, ""));
str1 = ss.str();
}
return str1;
}
int main()
{
string st = multiply("123456789", "987654321");
cout << st << endl;
return 0;
}