題目鏈接：
https://leetcode-cn.com/problems/multiply-strings/
難度：中等
43. 字串相乘
給定兩個以字串形式表示的非負整數 num1 和 num2，返回 num1 和 num2 的乘積，它們的乘積也表示爲字串形式。
範例 1:
輸入: num1 = "2", num2 = "3"
輸出: "6"
範例 2:
輸入: num1 = "123", num2 = "456"
輸出: "56088"
說明：
num1 和 num2 的長度小於110。
num1 和 num2 只包含數位 0-9。
num1 和 num2 均不以零開頭，除非是數位 0 本身。
不能使用任何標準庫的大數型別（比如 BigInteger）或直接將輸入轉換爲整數來處理。
不算難 做出來了 但是！ 爲什麼我寫的執行時間賊高？！ 日 終究還是菜！
class Solution {
public:
// 這個 addString 之前做過
string addStrings(string num1, string num2) {
int len1 = num1.size();
int len2 = num2.size();
int i = len1 - 1, j = len2 - 1;
int c = 0;
string res;
while (i >= 0 && j >= 0)
{
int a = num1[i--] - '0' + num2[j--] - '0' + c;
res += a % 10 + '0';
c = a / 10;
}
while (i >= 0) {
int a = num1[i--] - '0' + c;
res += a % 10 + '0';
c = a / 10;
}
while (j >= 0) {
int a = num2[j--] - '0' + c;
res += a % 10 + '0';
c = a / 10;
}
if (c > 0) {
res += c + '0';
}
reverse(res.begin(), res.end());
return res;
}
string multiply(string num1, string num2) {
if(num1=="0"||num2=="0"){
return "0";
}
string ans="0";
int n1=num1.size();
int n2=num2.size();
for(int i=n2-1;i>=0;--i){
string cur="";
// 進位標誌
int add=0;
int y=num2.at(i)-'0';
// num1
for(int j=n1-1;j>=0;--j){
int x=num1.at(j)-'0';
int num=x*y+add;
cur+=(num%10+'0');
add=num/10;
}
if(add){
cur+=(add+'0');
}
reverse(cur.begin(),cur.end());
for(int k=n2-1;k>i;--k){
cur+="0";
}
ans=addStrings(ans,cur);
}
return ans;
}
};
發現一個更優的解法（感覺靠我自己想不出來這種解法。。。 至少現在不行 ）
乘法 可以手動模擬一下
class Solution {
public:
string multiply(string num1, string num2) {
if(num1=="0"||num2=="0"){
return "0";
}
int n1=num1.size();
int n2=num2.size();
// n1位*n2位 最大是n1+n2位的 最小是n1+n2-1位的
// 記錄每一位的值 最左側位最高位
vector<int> result(n1+n2,0);
// 列舉 num1和num2
for(int i=n1-1;i>=0;--i){
int x=num1.at(i)-'0';
for(int j=n2-1;j>=0;--j){
int y=num2.at(j)-'0';
// 爲什麼是i+j+1？
// 可以試一下 num1[i] * num2[j]
// (i ,j 對數值來說(從右向左)分別是第n1-i n2-j 位 )
// 對於result來說應該在(下標)：(n1+n2)-(n1-i+n2-j-1)=i+j+1
// 注意此處沒有考慮進位 如 6*9 等
// 所以result中可能存在result[x]>10
result[i+j+1]+=x*y;
}
}
// 去除每一位中大於10的數值
for(int i=n1+n2-1;i>0;--i){
result.at(i-1)+=result.at(i)/10;
result.at(i)%=10;
}
string ans="";
int i=0;
if(!result.at(i)){
i=1;
}
while(i<n1+n2){
ans+=(result.at(i)+'0');
i++;
}
return ans;
}
};