一，知识点
1. 字符串相关知识（可看这篇☞《从零开始实现 std::string：让你更深入地了解字符串的本质》）
2. 相关题博客（《 leetcode415. 字符串相加》）
二， 题目(中等）
给定两个以字符串形式表示的非负整数 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本身。
三，思路
回想两个数num1和num2是怎么相乘的？
从低位到高位num2单个数依次乘num1
大于9就进位，下一个数乘num1后得加上进位的数重复运算
暴力的我😂
于是我只要像字符相加那样，设置进位变量，保留每单个数相乘的结果的变量
每下一个位时，就需要注意在结果后需要多加个0，因为位数的改变
再把每次的结果相加（利用那道字符串相加的题的思路）就是相乘的结果
于是这就是我的代码
#include <iostream> using namespace std; string addstr(string num1, string num2) { int i = num1.size() - 1; int j = num2.size() - 1; int carry = 0; string res; while (i >= 0 || j >= 0 || carry != 0) { int n1 = 0, n2 = 0; if (i >= 0) n1 = num1[i--] - '0'; if (j >= 0) n2 = num2[j--] - '0'; int sum = n1 + n2 + carry; carry = sum / 10; res.insert(0, 1, '0' + sum % 10); } return res; } string mulpro(string &a,char b,int &temp) { string mulsumgap; for(int j=a.size()-1;j>=0;--j) { mulsumgap=to_string(((b-'0')*(a[j]-'0')+ temp)%10) + mulsumgap; temp=((b-'0')*(a[j]-'0')+ temp)/10 ; } if(temp!=0) { mulsumgap= to_string(temp)+mulsumgap; temp=0; } return mulsumgap; } string multiply(string num1, string num2) { if(num1=="0"||num2=="0") return "0"; if(num1=="1") return num2; if(num2=="1") return num1; if(num1.length() < num2.length()) //大数×小数，效率高一些 swap(num1,num2); string mulsum; string resstr; for(int j=num1.size()-1;j>=0;--j) { int temp=0; for(int i=num2.size()-1;i>=0;--i) { mulsum=mulpro(num1,num2[i],temp); if(i!=num2.size()-1) { mulsum.append(num2.size()-i-1,'0'); resstr=addstr(mulsum,resstr); } else resstr=mulsum; mulsum = ""; } } if(resstr[0]=='0'&&resstr.size()!=1) resstr.erase(0); return resstr; } //本地测试 int main() { string num1="123"; string num2="456"; cout<<multiply(num1,num2); return 0; }
我设置了一个mulpro函数计算每次相乘的结果
当它不是个位数乘num1时就在后面插入0
再利用字符串相加的函数（这个函数在上面提到过）完成字符串相加
然后注意结果的字符串中第一个字符不能为0（除非只有一个字符）
虽然在本地可以跑通，但是在力扣上面超时了我哭死😭
优化后
这让我想起了动态规划的算法，开辟新数组，以空间换时间的做法
那么我们只要开辟一个大到足够装下结果的字符数组
然后将这个数组当作计算的自留地
每次相乘的结果保留在相应位置
需要相加时就取出相应位置的数进行相加
最后再把前面多余的0给删除
class Solution { public: string multiply(string num1, string num2) { if(num1=="0"||num2=="0")return "0"; if(num1=="1") return num2; if(num2=="1") return num1; if(num1.length() < num2.length()) //大数×小数，效率高一些 swap(num1,num2); string resstr(num1.size()+num2.size(),'0'); for(int j=num1.size()-1;j>=0;--j) { int temp=0; for(int i=num2.size()-1;i>=0;--i) { int mul_pro=(num1[j]-'0')*(num2[i]-'0')+(resstr[i+j+1]-'0')+temp; temp=mul_pro/10; mul_pro= mul_pro%10; resstr[i+j+1]=char(mul_pro+'0'); } if(temp>0)resstr[j]=char(temp+'0'); } int i = 0; while(resstr[i] == '0') i++; return resstr.substr(i,num1.size()+num2.size()-i); } };
四，AC代码
class Solution { public: string multiply(string num1, string num2) { if(num1=="0"||num2=="0")return "0"; if(num1=="1") return num2; if(num2=="1") return num1; if(num1.length() < num2.length()) //大数×小数，效率高一些 swap(num1,num2); string resstr(num1.size()+num2.size(),'0'); for(int j=num1.size()-1;j>=0;--j) { int temp=0; for(int i=num2.size()-1;i>=0;--i) { int mul_pro=(num1[j]-'0')*(num2[i]-'0')+(resstr[i+j+1]-'0')+temp; temp=mul_pro/10; mul_pro= mul_pro%10; resstr[i+j+1]=char(mul_pro+'0'); } if(temp>0)resstr[j]=char(temp+'0'); } int i = 0; while(resstr[i] == '0') i++; return resstr.substr(i,num1.size()+num2.size()-i); } };
五，小结
虽然看起来简单，实际动起手来就会发现有大大小小的情况没有考虑清楚，何以解忧？唯有勤！
