2024.09.18 leetcode 每日一题
二进制求和
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
https://leetcode.cn/problems/add-binary/description/
代码一，尝试使用笨办法，会造成溢出
class Solution {
public:string addBinary(string a, string b) {int len1 = a.length();int len2 = b.length();long long A=0;long long B=0;for(int i=len1-1;i>=0;i--){A +=(a[i] - '0') *pow(2,len1-1-i);}for(int j=len2-1;j>=0;j--){B +=(b[j] - '0')*pow(2,len2-1-j);}long long C=A+B;if(C==0){string c="0";return c;}string c;while(C!=0){int m = C%2; c+=(m+'0');C=C/2;}string reversed_c(c.rbegin(), c.rend());return reversed_c;}
};
注意，对于字符串的反转可以使用：
string reversed_c(c.rbegin(), c.rend());
按照这个思路，先对于ab字符串反转，然后按位相加，最后考虑进位问题，这个思路还是有点问题
看到一个大佬的题解
class Solution {
public:string addBinary(string a, string b) {if (b.size() > a.size()) {return addBinary(b, a); // 这里先确保第一个数不短于第二个数}int m = a.size(), n = b.size(), carry = 0;for (int i = 0; i < m; i++) {if (n - 1 - i < 0) {if (carry == 0) break;} else {carry += b[n - 1 - i] - '0';}carry += a[m - 1 - i] - '0';a[m - 1 - i] = '0' + (carry % 2);carry >>= 1;}return carry ? '1' + a : a;}
};
函数分析：
- 首先进行长度比较，如果
b的长度大于a的长度，就交换两个参数的位置，确保第一个参数（这里是a）不短于第二个参数。这样做是为了在后续的循环中简化处理，因为在处理时是以较长的字符串为基准进行遍历。 - 然后确定两个字符串的长度
m和n，以及进位carry初始值为 0。 - 接着进入循环，循环从长字符串
a的最后一个字符开始向前遍历。- 如果当前索引对应的位置超出了短字符串
b的范围，即n - 1 - i < 0，此时如果进位carry为 0，则说明没有更多的进位需要处理，可以直接跳出循环。 - 如果当前索引对应的位置在短字符串
b的范围内，则将短字符串b对应位置的字符值转换为数字（通过减去字符’0’）累加到进位carry中。 - 同时，将长字符串
a对应位置的字符值也转换为数字累加到进位carry中。 - 然后更新长字符串
a对应位置的字符为当前进位和的结果对 2 取余后再加上字符’0’，即得到该位置的新二进制值。 - 最后更新进位
carry为其当前值右移一位，相当于除以 2，以准备下一位的计算。
- 如果当前索引对应的位置超出了短字符串
- 循环结束后，如果进位
carry不为 0，则在结果字符串a的前面添加一个字符’1’，表示最高位有进位；否则直接返回a作为最终的结果字符串。
下面是一种常规思路，上面的思路看不懂可以看下面这个
class Solution {
public:string addBinary(string a, string b) {int al = a.size();int bl = b.size();while(al < bl) //让两个字符串等长，若不等长，在短的字符串前补零，否则之后的操作会超出索引{a = '0' + a;++ al;}while(al > bl){b = '0' + b;++ bl;}for(int j = a.size() - 1; j > 0; -- j) //从后到前遍历所有的位数，同位相加{a[j] = a[j] - '0' + b[j];if(a[j] >= '2') //若大于等于字符‘2’，需要进一{a[j] = (a[j] - '0') % 2 + '0';a[j-1] = a[j-1] + 1;}}a[0] = a[0] - '0' + b[0]; //将ab的第0位相加if(a[0] >= '2') //若大于等于2，需要进一{a[0] = (a[0] - '0') % 2 + '0';a = '1' + a;}return a;}
};
``