【Leetcode】字符串之二进制求和、字符串相乘

---

算法原理

这两道题都是属于算法里一种经典题型：高精度加/减/乘/除法，需要我们模拟加/减/乘/除 列竖式运算。

二进制求和

题目链接

题目链接

题目描述

解题思路

先创建两个指针分别指向字符串末尾，创建变量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;}
};

以上就是小编分享的全部内容了，如果觉得不错还请留下免费的关注和收藏
如果有建议欢迎通过评论区或私信留言，感谢您的大力支持。
一键三连好运连连哦~~