題目
給定兩個以字符串形式表示的非負(fù)整數(shù) num1 和 num2舌涨，返回 num1 和 num2 的乘積叮喳，它們的乘積也表示為字符串形式塑顺。
示例 1:
輸入: num1 = "2", num2 = "3"
輸出: "6"
示例 2:
輸入: num1 = "123", num2 = "456"
輸出: "56088"
說明：
num1 和 num2 的長度小于110淳附。
num1 和 num2 只包含數(shù)字 0-9帮辟。
num1 和 num2 均不以零開頭打洼，除非是數(shù)字 0 本身龄糊。
不能使用任何標(biāo)準(zhǔn)庫的大數(shù)類型（比如 BigInteger）或直接將輸入轉(zhuǎn)換為整數(shù)來處理。
思路
1募疮、字符轉(zhuǎn)轉(zhuǎn)整數(shù)炫惩，整數(shù)相乘，乘完轉(zhuǎn)字符轉(zhuǎn)阿浓，這樣做發(fā)現(xiàn)數(shù)太大的話會一出
class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
long int temp;
string res;
long long IntRes = 0;
long int IntNum1 = string2int(num1);
long int IntNum2 = string2int(num2);
IntRes = IntNum1 * IntNum2;
res = int2string(IntRes);
return res;
}
int string2int (string StrNum)
{
long int Intnum = 0;
long int temp = 0;
for (int i = 0; i < StrNum.size(); i++)
{
temp = (StrNum[i] - '0');
Intnum = Intnum * 10 + temp;
}
return Intnum;
}
string int2string(long int nums)
{
string res;
long int temp;
while (nums > 0)
{
temp = nums % 10;
nums /= 10;
res = res + char(temp + '0');
}
int j = res.size() - 1;
string tem = "";
for (int i = 0; i < res.size(); i ++)
{
tem = tem + res[j];
j--;
}
return tem;
}
};
2他嚷、分別對每一位進(jìn)行運(yùn)算，每一次運(yùn)算都要記錄下來余數(shù)和進(jìn)位的數(shù)，方便進(jìn)行下次計(jì)算筋蓖。str[i + j + 1]是num1[j]和num2[i]相乘計(jì)算的那一位卸耘。
class Solution2
{
public:
string multiply(string num1, string num2)
{
if (num1 == "0" || num2 == "0") return "0";
int size1 = num1.size(), size2 = num2.size();
string str(size1 + size2, '0');
for (int i = size2 - 1; i >= 0; --i)
{
int AddNum = 0, LostNum = 0;
for (int j = size1 - 1; j >= 0; --j)
{
int Temp1 =(num2[i] - '0') * (num1[j] - '0') + AddNum;
AddNum = Temp1 / 10;
Temp1 = Temp1 % 10;
int Temp2 = str[i + j + 1] - '0' + LostNum + Temp1;//對上一次的進(jìn)位和這次的余數(shù)進(jìn)行相加
str[i + j + 1] = Temp2 % 10 + '0';
LostNum = Temp2 / 10;
}
str[i] += LostNum + AddNum;
}
if (str[0] == '0')
{
str = str.substr(1, str.size());
}
return str;
}
};
