算法原理
这两道题都是属于算法里一种经典题型：高精度加/减/乘/除法，需要我们模拟加/减/乘/除 列竖式运算。
二进制求和
题目链接
题目描述
解题思路
先创建两个指针分别指向字符串末尾，创建变量t存储每次加法的结果。 首先一个while循环当两个字符串都遍历完并且变量值为0时跳出循环。
我们做加法是从后往前加，所以先创建两个指针分别指向字符串末尾，把指向的值分别加到变量t中，注意这里我们a[end]访问到的是字符’0’或’1’的ascll码值，所以它还要减去’0’。
加完后不要忘记end–。
得到的值t还要模2才能把值+=到字符串中，因为二进制加法逢二进一，注意还要把得到的值加’0‘得到字符1的ASCII码值，因为我们需要加的是字符1，再把t除二赋给t当作进位参与下一次加法运算。
因为s一直的尾插，所以最后还要把s逆置一下得到结果。
代码
class Solution {
public:
string addBinary(string a, string b) {
string s;
int end1 = a.size() - 1;
int end2 = b.size() - 1;
int t = 0;
while (end1 >= 0 || end2 >= 0 || t)
{
if(end1 >= 0)
t += a[end1--] - '0';
if(end2 >= 0)
t += b[end2--] - '0';
s += t % 2 + '0';
t = t / 2;
}
reverse(s.begin(), s.end());
return s;
}
};
字符串相乘
题目链接
题目描述
解题思路
这道题解法是我们依次相乘后的结果先不进位，乘完后一起相加得到结果后再进位，在加之前进位和加之后进位最后得到的结果是一样的，无进位相乘再相加代码编写会更便捷。
步骤一：
先将原始字符字符串逆序，因为我们要将字符串数据相乘得到的数据存放到整型数组
vector中，逆序两个字符串下标相加正好就和要存放位置的vector的下标对应。
步骤二：
两层for循环搞定无进位相加，我们要开一个动态数组vector来存放无进位相加的结果，动态数组大小为m + n -1,这里我们考虑极限情况，下面999*999得到的结果也只是五个数，所以用m + n - 1来存是完全足够的，下标的对应关系和我们之前分析的一样。
这里还要特别注意因为题目的num1和num2是string对象，所以里面存的数据类型的char，也就是数字对应的ASCII码值，所以[]取到的值还要减去字符0对应的 ASCII码值。
步骤三：
这里就需要处理无进位相加的结果，这里思路和我们上一题二进制相加很类似，定义一个cur记录vector下标，定义一个t记录处理进位后的结果，这里也要注意把t尾插到string里要先加’0’。
步骤四：
这里是乘法，所以要比上一题多一个步骤，处理前导零。如果两个乘数有其中一个为0那么结果就为单独一个0，处理前导零之前有可能有多个0，具体几个0取决于m+n-1的结果，那么就需要将多余的0删除。
最后再将string逆置，就得到结果啦。
代码
class Solution {
public:
string multiply(string n1, string n2) {
//1、准备工作
reverse(n1.begin(),n1.end());
reverse(n2.begin(),n2.end());
size_t m = n1.size();
size_t n = n2.size();
//2、无进位相加
vector<int> v(m + n - 1);
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
//字符ASCII码转换成数字
v[i + j] += (n1[i] - '0') * (n2[j] - '0');
}
}
//3、处理进位
size_t cur = 0, t = 0;
string ret;
while(cur < m + n - 1 || t != 0)
{
//避免越界
if(cur < m + n - 1)
t += v[cur++];
//数字转换成ASCII码
ret += (t % 10) + '0';
t = t / 10;
}
//4、处理前导零
while(ret.size() > 1 && ret.back() == '0')
ret.pop_back();
reverse(ret.begin(), ret.end());
return ret;
}
};
以上就是小编分享的全部内容了，如果觉得不错还请留下免费的关注和收藏
如果有建议欢迎通过评论区或私信留言，感谢您的大力支持。
一键三连好运连连哦~~
