题目
给定两个以字符串形式表示的非负整数 num1
和 num2
,返回 num1
和 num2
的乘积,它们的乘积也表示为字符串形式。
**注意:**不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
提示:
1 <= num1.length, num2.length <= 200
num1
和num2
只能由数字组成。num1
和num2
都不包含任何前导零,除了数字0本身。
普通竖式法
思路
第一种方法的主要思路就是模拟我们平时手算的计算过程,其主要步骤如下:
首先我们实现一个可以两个string类型可以相加的子函数。
依次将每一个乘数与被乘数的结果相加就是最终结果。
关键有两点:
如果做string类型的乘法?
其实我们每次的乘法都是单位数和(单位数或者多位数)相乘,那么我们可以把乘法看作是单位数次(多位数)相加。
如何在乘数与被乘数的结果后面补充合适个数的零?
乘数倒数第n位与被乘数的结果后面补充n-1个零。
AC代码
class Solution {
public:
string multiply(string num1, string num2) {
if ("0" == num1 || "0" == num2){
return "0";
}
string ret;
int flag = 0;
for (int i = num2.size() - 1; i >= 0; i--)
{
string tmp;
int count = num2[i] - '0';
for (int j = 0; j < count; j++)
{
tmp = StringAdd(tmp, num1);
}
for (int k = 0; k < flag; k++)
{
tmp.push_back('0');
}
ret = StringAdd(ret, tmp);
flag++;
}
return ret;
}
string StringAdd(string a, string b){
int i = a.size() - 1;
int j = b.size() - 1;
string ret;
int flag = 0;
while (i >= 0 || j >= 0){
int num1 = 0;
if (i >= 0)
{
num1 = a[i] - '0';
i--;
}
int num2 = 0;
if (j >= 0)
{
num2 = b[j] - '0';
j--;
}
int add = num1 + num2 + flag;
if (add > 9)
{
flag = 1;
add -= 10;
}
else
{
flag = 0;
}
ret.push_back('0' + add);
}
if (1 == flag)
{
ret.push_back('1');
}
reverse(ret.begin(), ret.end());
return ret;
}
};
优化竖式法
思路
如果我们先不进位,最后一起进位的话就可以用一个整形数组暂时保存计算结果
这个数组应该开辟多大的空间?
如果m = num1.size() n = num2.size()
假设num1长度是1,num2长度是1,那么最小长度为1,即为m+n-1;最大长度为2,即为m+n。
如何在数组合适的位置加上计算结果?
通过观察不难发现,被乘数的下标为i,乘数的下标为j,它们相乘的结果应该放在数组下标为i+j+1的位置。
AC代码
class Solution {
public:
string multiply(string num1, string num2) {
if ("0" == num1 || "0" == num2)
{
return "0";
}
int sz_1 = num1.size();
int sz_2 = num2.size();
string ret;
vector<int> v(sz_1+sz_2, 0);
for (int i = num2.size() - 1; i >= 0; i--){
int x2 = num2[i] - '0';
for (int j = num1.size() - 1; j >= 0; j--){
int x1 = num1[j] - '0';
v[i+j+1] += x1 * x2;
}
}
int flag = 0;
for (int i = sz_1 + sz_2 - 1; i >= 0; i--){
v[i] += flag;
flag = v[i] / 10;
v[i] %= 10;
}
if (v[0] != 0){
ret.push_back('0' + v[0]);
}
for (int i = 1; i < sz_1 + sz_2; i++)
{
ret.push_back('0' + v[i]);
}
return ret;
}
};