题目链接:大数乘法_牛客题霸_牛客网 (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;
}
};
三、反思与改进
这道题的思路蛮清晰的,基本正确,但是却没想到是用了临时变量间接导致两数相加过大,超出了数据范围,导致有些数据很大的样例过不去,还以为是数字过大有其他的做法,其实并不是,模板已经能解决所有数据了。本质还是模板没有完全弄明白并熟记,这是妥妥送分题,要保证模板题不能再出错!