当前位置：首页 > news >正文

2024.09.18 leetcode 每日一题

news 来源：原创 2024/9/24 4:55:27

二进制求和

给你两个二进制字符串 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;}
};
``