2020年7月15日 周三 天气晴 【不悲叹过去，不荒废现在，不惧怕未来】
题目简介
LeetCode 43. 字符串相乘
记得我第一次接触大数相乘的时候，还是在大二刚进实验室的时候，师兄两天给我们培训完Ｃ语言后布置了几道题，里面就有这个大数相乘，当时可以说啥也不会啊，没想到终究还是绕不过这道题hhh~这里介绍两种方法，方法一比较好想，方法二需要点技巧。
解法1. 将所有数据不进位直接存入数组，最后统一进位（记住这种即可）
- 把两个数用数组 a, b 来存储，并且反转（从个位开始乘）。
- 对于 a 的第 i 位 和 b 的第 j 位相乘的结果存储在 c[i + j] 上，即 c[i + j] += a[i] * b[j]。这里用加号是因为有多种情况都会映射到 i + j 位上。
- 最后，从 c 的低位向高位整理，c[i + 1] = c[i] / 10, c[i] %= 10。
举个栗子：
代码：
class Solution {
public:
string multiply(string num1, string num2) {
int len1 = num1.size(), len2 = num2.size();
// 不进位直接存放在数组中
vector<int> num(len1+len2);
for(int i=len1-1;i>=0;--i){
for(int j=len2-1;j>=0;--j){
int n1 = num1[i] - '0', n2 = num2[j] - '0';
num[i+j+1] += n1*n2;
}
}
// 开始进位
string ans;
int c = 0, r = 0;
for(int i=len1+len2-1;i>=0;--i){
r = (num[i]+c)%10;
c = (num[i]+c)/10;
ans = to_string(r) + ans;
}
// 去除前导0
while(ans.size()>1 && ans[0]=='0') ans.erase(ans.begin());
return ans;
}
};
解法2. 竖式乘法（代码简洁，但是细节不好理解）
首先，长度为 m 的数乘以长度为 n 的数的结果不超过 m+n。
接下来看一下两数相乘的计算过程，从右向左，将数2中的每一位的数与数1相乘，最后将结果相加。下图演示的是两数相乘的整个过程，从下图中，我们可以得到，对于num[i] *num[j]，数1中的第 i 位数字与数2中的第 j 位数字相乘的结果只会存放在第【i+j】和【i+j+1】这两位上。然后再竖着相加，就能得到结果了。
核心思想：
每次只更新低位（相对于数字而言）【i+j+1】上的数，而不管高位【i+j】上的数是否超过10（即使超过了10 ，字符也能存储，并且后面都会对超过10的位置进行数字更新，同时
首位字符代表的数字一定不会超过10
，不然就违反了 ”
长度为 m 的数乘以长度为 n 的数的结果不超过 m+n
” 这句话）。
class Solution {
public:
string multiply(string num1, string num2) {
int len1 = num1.size(), len2 = num2.size();
string ans(len1+len2,'0');
for(int i=len1-1;i>=0;--i){
for(int j=len2-1;j>=0;--j){
/* 1. 这里只加上低位 (ans[i+j+1]-'0')，是因为高位可以暂时不管，即使超过了10 ，
字符也能存储（计算字符和 '0' 的偏移量就是数字的值）*/
int tmp = (ans[i+j+1]-'0') + (num1[i]-'0')*(num2[j]-'0');
ans[i+j+1] = tmp%10 + '0';
/* 2. 这里之所以没考虑进位，是因为第 1 点 */
/* 3. 另外，首位不用担心相加会超过10，因为之前说了，
长度为 m 的数乘以长度为 n 的数的结果不超过 m+n，所以首位一定不会进位，否则就超过 m+n 了 */
ans[i+j] += tmp/10;
}
}
while(ans.size()>1 && ans[0]=='0') ans.erase(ans.begin());
return ans;
}
};
刚看完代码，感觉 res[i+j] += temp/10; 这一步好像没有进位，不过仔细想想会发现，这一步即使相加超过了 10 也不用进位，因为后面再次执行这一步
int tmp = (ans[i+j+1]-'0') + (num1[i]-'0')*(num2[j]-'0');
的时候
会把没有进的位加上去
。另外
首位不用担心相加会超过10
，因为之前说了，长度为 m 的数乘以长度为 n 的数的结果不超过 m+n，所以首位一定不会进位，否则就超过 m+n 了。
参考文献
https://leetcode-cn.com/problems/multiply-strings/solution/si-lu-qing-xi-by-lllllliuji-2/
https://leetcode-cn.com/problems/multiply-strings/solution/c-shu-shi-cheng-fa-dai-ma-jian-ji-you-ya-yi-dong-b/
https://leetcode.com/problems/multiply-strings/discuss/17605/Easiest-JAVA-Solution-with-Graph-Explanation
https://blog.csdn.net/kangkanglou/article/details/79894208
十分感谢以上这些大神们。