题目链接：大数乘法_牛客题霸_牛客网 (nowcoder.com)
一、分析题目
根据列竖式运算的过程模拟即可，但是我们可以改进⼀下列竖式的过程：
- 先计算⽆进位相乘并且相加后的结果；
- 然后再处理进位。
细节：题目所给的两个字符串需要提前逆序，方便从低位开始进行运算，其次要注意字符和数字的转化，还有进位和前导 0 的处理。
二、代码
//看了题解之后AC的代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 第一个整数 * @param t string字符串 第二个整数 * @return string字符串 */ string solve(string s, string t) { int n=s.size(), m=t.size(); reverse(s.begin(), s.end()); reverse(t.begin(), t.end()); string res; vector<int> sum(n+m-1); for(int i=0; i<n; i++) for(int j=0; j<m; j++) sum[i+j]+=(s[i]-'0')*(t[j]-'0'); int k=0; int i=0; while(i<n+m-1) { k+=sum[i]; res+=(k%10)+'0'; k/=10; i++; } while(k) { res+=(k%10)+'0'; k/=10; } while(res.size()>1 && res.back()=='0') res.pop_back(); reverse(res.begin(), res.end()); return res; } }; //值得学习的代码 class Solution { public: string solve(string s, string t) { reverse(s.begin(), s.end()); reverse(t.begin(), t.end()); int m = s.size(), n = t.size(); vector<int> tmp(m + n); // 1. ⽆进位相乘相加 for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { tmp[i + j] += (s[i] - '0') * (t[j] - '0'); } } // 2. 处理进位 int c = 0; string ret; for(auto x : tmp) { c += x; ret += c % 10 + '0'; c /= 10; } while(c) { ret += c % 10 + '0'; c /= 10; } // 3. 处理前导零 while(ret.size() > 1 && ret.back() == '0') ret.pop_back(); reverse(ret.begin(), ret.end()); return ret; } };
三、反思与改进
这道题的思路蛮清晰的，基本正确，但是却没想到是用了临时变量间接导致两数相加过大，超出了数据范围，导致有些数据很大的样例过不去，还以为是数字过大有其他的做法，其实并不是，模板已经能解决所有数据了。本质还是模板没有完全弄明白并熟记，这是妥妥送分题，要保证模板题不能再出错！
