刷题
- Leetcode 415 字符串相加
- 题目描述
- 思路一（模拟大法版！！！）
- Leetcode 34 字符串相乘
- 题目描述
- 思路一（模拟大法版）
- Thanks♪(･ω･)ﾉ谢谢阅读！！！
- 下一篇文章见！！！
Leetcode 415 字符串相加
题目描述
逻辑很简单，对应位置相加，并进位即可。
思路一（模拟大法版！！！）
本题我们只需要对两个大整数模拟「竖式加法」的过程。竖式加法就是我们平常学习生活中常用的对两个整数相加的方法，回想一下我们在纸上对两个整数相加的操作，是不是将相同数位对齐，从低到高逐位相加，如果当前位和超过 10，则向高位进一位？因此我们只要将这个过程用代码写出来即可。
class Solution {
public:
string addStrings(string num1, string num2) {
int carry = 0;
string::reverse_iterator it1 = num1.rbegin() ;
string::reverse_iterator it2 = num2.rbegin() ;
string res = "";
while (it1 != num1.rend() || it2 != num2.rend() || carry) {
int n1 = 0, n2 = 0;
if (it1 != num1.rend()) {
n1 = *it1 - '0';
it1++;
}
if (it2 != num2.rend()) {
n2 = *it2 - '0';
it2++;
}
int result = n1 + n2 + carry;
res += (result % 10) + '0';
carry = result / 10;
}
reverse(res.begin(), res.end());
return res;
}
};
来看效果：
非常好！！！！！！
过啦！！！！！！！！
Leetcode 34 字符串相乘
题目描述
根据描述，这道题实际上就是模拟一下乘法运算，这是又又又用到了乘法器原理（实际上就是竖式运算），不得不说竖式运算真的是神！！！如果要用竖式乘法就要分布相乘，然后在加到一起，这时又会用到字符串相加的知识。所以这道题可谓一箭双雕。该题的难点应该是如何保证模拟过程的顺利进行。
思路一（模拟大法版）
- 两个乘数选择其一进行逐个相乘操作
- 每次相乘获得一个数 并 对应相对的数量级
- 每次相加到一起
这样就完成我们的操作。
如果num和num2之一是0，则直接将0作为结果返回即可。
如果num和num2都不是0，则可以通过模拟「竖式乘法」的方法计算乘积。从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。这道题中，被乘数是 num，乘数是num2。
需要注意的是，num2除了最低位以外，其余的每一位的运算结果都需要补0。
我们进行一下图解：
这样就看见进行我们的代码编写工作了！！！
干就完了！ 如果看不出错误请在VS中进行调试哦！
class Solution {
public:
//求和函数
string addStrings(string num1, string num2) {
//进位
int carry = 0;
//迭代器版
string::reverse_iterator it1 = num1.rbegin();
string::reverse_iterator it2 = num2.rbegin();
string res = "";
//加完为止
while (it1 != num1.rend() || it2 != num2.rend() || carry) {
// 进行计算
int n1 = 0, n2 = 0;
if (it1 != num1.rend()) {
n1 = *it1 - '0';
it1++;
}
if (it2 != num2.rend()) {
n2 = *it2 - '0';
it2++;
}
// 结果
int result = n1 + n2 + carry;
//该位置 为结果取余数
res += (result % 10) + '0';
//进位
carry = result / 10;
}
//不要忘记反转！！！
reverse(res.begin(), res.end());
return res;
}
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
//乘数1
int p1 = num1.size() - 1;
string ans = "0";
while (p1 >= 0) {
//乘数2
int p2 = num2.size() - 1;
//开始乘
//数字 1 进位数 结果
int carry = 0; string tmp = "";
while (p2 >= 0 || carry) {
//进行计算
int n1 = 0, n2 = 0;
if (p1 >= 0) {
n1 = num1[p1] - '0';
}
if (p2 >= 0) {
n2 = num2[p2] - '0';
p2--;
}
//该步的结果
int result = n1 * n2 + carry;
tmp += result % 10 + '0';
carry = result / 10;
}
//不要忘记反转！！！
reverse(tmp.begin(), tmp.end());
//对应数量级一定要搞清楚
for (int i = 0; i < num1.size() - p1 - 1; i++) {
tmp += '0';
}
//加到答案中
ans = addStrings(ans, tmp);
p1--;
}
return ans;
}
};
来看效果：
顺利通过！！！
为我们鼓掌！！！！！！！
送给大家一句我非常喜欢的名言：
我从来不相信什么懒洋洋的*。我向往的*是通过勤奋和努力实现的更广阔的人生。——山本耀司