Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
Note:
The length of both num1 and num2 is < 110. Both num1 and num2 contains only digits 0-9. Both num1 and num2 does not contain any leading zero. You must not use any built-in BigInteger library or convert the inputs to integer directly.
题意:给定两个数字(string型),返回二者之积(string型)
解题思路:模拟乘法,分别计算两个数字各位乘积,存在向量tmp中,然后进行进位处理,最后返回结果。 两个m位和n位数字相乘,结果最大不超过m+n位。
AC代码:
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
class Solution {
public:
string multiply(string num1, string num2) {
int n1 = num1.size(), n2 = num2.size();
if (n1 == 0 || n2 == 0)
return "";//空的话返回空
if (num1[0] == '0' || num2[0] == '0')
return "0";//如果有0的话返回"0"
string res;
vector<int> tmp(n1 + n2, 0);//tmp长度为m+n,初始化为0
int k = n1 + n2 - 2;
for (int i = 0; i<n1; i++)
{
for (int j = 0; j<n2; j++)
{
tmp[k - i - j] += (num1[i] - '0')*(num2[j] - '0');//这里顺序不要弄错,数字高位在前,保存到tmp向量末尾
}
}
int c = 0;
for (int i = 0; i<n1 + n2; i++)//处理进位
{
tmp[i] += c;
c = tmp[i] / 10;
tmp[i] %= 10;
}
int i = k + 1;
//从不是0的最高位算起(因为结果可能小于m+n位)
while (tmp[i] == 0)
i--;
for (; i >= 0; i--)
res.push_back(tmp[i] + '0');
return res;
}
};
void main(void)
{
string a = "1", b = "1";
Solution p;
string res;
res = p.multiply(a, b);
cout << res.c_str();
system("pause");
}