一. 这题估计被我写复杂了,但是想法比较简单.
class Solution { public: string addBinary(string a, string b) { stack<char> tmp; int i = a.length() - 1, j = b.length() - 1, cc = 0; //x和y代表当前位置上的值是多少. int x,y; //因为两个二进制字符串长度不一定相等. while (i >= 0 || j >= 0) { //如果短的字符串小于0了, //就在他的前面补0. if (i < 0) x = 0; //因为a和b是字符串, //所以需要减去'0'的ascii值得到数字. else x = a[i] - '0'; if (j < 0) y = 0; else y = b[j] - '0'; //如果加上进位大于等于2,也有可能是3. if (x + y + cc >= 2) { if(x + y + cc == 2){ //压栈. tmp.push('0'); cc = 1; } else{ tmp.push('1'); cc = 1; } } else { if (x + y + cc == 0) tmp.push('0'); else tmp.push('1'); cc = 0; } //同时更新i和j,去计算下一位的值. i--; j--; } //如果还有进位,则再push一个1. if (cc == 1) { tmp.push('1'); } string res = ""; //这里解释下为何用栈这种数据结构, //因为加法是从字符串尾部往前加, //赋值字符串时从头开始赋值,符合后进先出, //先进后出. while (!tmp.empty()) { res += tmp.top(); tmp.pop(); } return res; } };不过时间还是挺可以的..........
二. 参考一下大神的解法,对比一下.
作者：guanpengchn 链接：https://leetcode-cn.com/problems/add-binary/solution/hua-jie-suan-fa-67-er-jin-zhi-qiu-he-by-guanpengch/
思路 1. 整体思路是将两个字符串较短的用 0 补齐，使得两个字符串长度一致，然后从末尾进行遍历计算，得到最终结果。
2. 本题解中大致思路与上述一致，但由于字符串操作原因，不确定最后的结果是否会多出一位进位，所以会有 2 种处理方式：
3. 第一种，在进行计算时直接拼接字符串，会得到一个反向字符，需要最后再进行翻转. 4. 第二种，按照位置给结果字符赋值，最后如果有进位，则在前方进行字符串拼接添加进位. 时间复杂度：O(n)
class Solution { public: string addBinary(string a, string b) { string ans; int cc = 0, i = a.size() - 1, j = b.size() - 1; while (i >= 0 || j >= 0) { int sum = cc; sum += (i >= 0 ? a[i--] - '0' : 0); sum += (j >= 0 ? b[j--] - '0' : 0); //利用to_string将数字转换成字符串. //利用stoi将字符串转换为数字. //类似十进制取个位十位,这里是二进制. ans += to_string(sum % 2); cc = sum / 2; } //判断最后需不需要补1. ans += (cc == 0 ? "" : "1"); //反转字符串. reverse(ans.begin(), ans.end()); return ans; } };