【字符串】二进制求和 && 字符串相乘
【字符串】二进制求和 && 字符串相乘
67. 二进制求和
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
输入:a = "11", b = "1"
输出："100"示例 2：
输入：a = "1010", b = "1011"
输出："10101"提示：
1 <= a.length, b.length <= 104a和b仅由字符'0'或'1'组成- 字符串如果不是
"0"，就不含前导零
解题思路：模拟
我们之前做过类似的求和问题，其实都是一样的，只不过这道题变成了字符串形式罢了，思路都还是一样的，只不过现在变成了逢二进一！
class Solution {
public:
string addBinary(string a, string b) {
int sum = 0;
int indexa = a.size() - 1, indexb = b.size() - 1;
string ret;
while(indexa >= 0 || indexb >= 0 || sum != 0)
{
if(indexa >= 0)
{
sum += (a[indexa] - '0');
indexa--;
}
if(indexb >= 0)
{
sum += (b[indexb] - '0');
indexb--;
}
// 使用模运算获取每次要加的数，然后让其除以二，有进位的话就被留下了！
ret += to_string(sum % 2);
sum /= 2;
}
reverse(ret.begin(), ret.end());
return ret;
}
};43. 字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意： 不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"提示：
1 <= num1.length, num2.length <= 200num1和num2只能由数字组成。num1和num2都不包含任何前导零，除了数字0本身。
解题思路：模拟 + 优化
对于相乘，如果我们是使用小学时候教的那种比如说 123 * 456，那么先拿 456 * 3 得到一个字符串，合并到结果字符串 ret 中，然后拿 456 * 2 得到一个字符串添加到结果字符串 ret 中，以此类推，其实这种方式是不太好搞的，因为这道题它给的是字符串，并且顺序是正序，我们在实际操作的时候就可能会有前导零啊，边界的情况，所以这种模拟方式需要优化一下！
我们可以每次拿 6 * 3、6 * 2、6 * 1，分别得到的就是 18、12、6，然后再拿 456 的第二位与 123 的每一位去相乘得到一个结果，最后再将这些结果进行累加放到数组中去，如下图所示：
接下来我们需要处理的就只是对这个结果集数组进行进位处理，也是很简单，最后就能得到结果！
不过我们其实可以一步到位，这里要利用一个结论，就是 两个数相乘的最大位数不会超过两个数的位数相加！所以利用这个结论，我们可以用一个字符串 ret，开辟 num1.size() + num2.size() 大小，然后将其都初始化为 0。
然后在处理相乘的每一个结果的时候，该位置对应在字符串 ret 中的位置就是 ret[i + j + 1]，然后顺便该位置的结果求其进位，累加到其前面的位置也就是 ret[i + j]，这样子就同时完成了相乘和进位的操作！
要注意的是在操作过程中，我们是对字符串的操作，所以需要 注意操作的字符是 '0'，而不是数字 0，它们的大小是不一样的！
最后还要注意的就是有可能整个结果字符串的位数是小于 num1.size() + num2.size() 的，也就是说有前导零，所以 返回结果的时候要将前导零去掉！
class Solution {
public:
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0")
return "0";
int n = num1.size() + num2.size();
string ret(n, '0'); // 创建一个两个字符串长度总和的字符串，然后初始化为'0'
for(int i = num1.size() - 1; i >= 0; --i)
{
for(int j = num2.size() - 1; j >= 0; --j)
{
int sum = (num1[i] - '0') * (num2[j] - '0') + (ret[i + j + 1] - '0'); // 先求出当前位置总和
ret[i + j + 1] = (sum % 10) + '0'; // 处理当前位置
ret[i + j] += sum / 10; // 处理进位
}
}
// 找到第一个非零元素
int i = 0;
while(i < n && ret[i] == '0')
i++;
return ret.substr(i);
}
};腾讯云开发者
