建设农产品网站总结ppt,哪里能找到网站,汉中专业网站建设公司,济南知名网站建设平台二进制求和
给你两个二进制字符串 a 和 b #xff0c;以二进制字符串的形式返回它们的和。
https://leetcode.cn/problems/add-binary/description/
代码一#xff0c;尝试使用笨办法#xff0c;会造成溢出
class Solution {
public:string addBinary(string a, string …二进制求和
给你两个二进制字符串 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 A0;long long B0;for(int ilen1-1;i0;i--){A (a[i] - 0) *pow(2,len1-1-i);}for(int jlen2-1;j0;j--){B (b[j] - 0)*pow(2,len2-1-j);}long long CAB;if(C0){string c0;return c;}string c;while(C!0){int m C%2; c(m0);CC/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;}
};
