文章目录
- 1.题目
- [67. 二进制求和](https://leetcode.cn/problems/add-binary/description/)
- 2.思路
- 3.代码
1.题目
67. 二进制求和
给你两个二进制字符串 a
和 b
,以二进制字符串的形式返回它们的和。
示例 1:
**输入:**a = "11", b = "1"
**输出:**"100"
示例 2:
**输入:**a = "1010", b = "1011"
**输出:**"10101"
2.思路
while
循环进行逐位相加,循环条件为 cur1 >= 0 || cur2 >= 0 || carry
,这意味着只要字符串 a
或 b
还有未处理的位,或者存在进位,就继续进行加法运算。
计算当前位的结果,将 carry
对 2 取余得到当前位的值(因为是二进制加法,结果只能是 0 或 1),并将其转换为字符添加到结果字符串 ret
中。
更新进位,将 carry
除以 2 得到新的进位,用于下一轮的加法运算。
3.代码
class Solution {
public:// 该函数用于实现两个二进制字符串的加法string addBinary(string a, string b) {// 用于存储最终的二进制加法结果string ret = "";// 控制进位,初始化为 0int carry = 0;// 指针 cur1 指向字符串 a 的最后一个字符int cur1 = a.size() - 1;// 指针 cur2 指向字符串 b 的最后一个字符int cur2 = b.size() - 1;// 当字符串 a 未遍历完 或 字符串 b 未遍历完 或 存在进位时,继续循环while (cur1 >= 0 || cur2 >= 0 || carry) {// 如果字符串 a 还未遍历完if (cur1 >= 0) {// 将当前字符转换为数字并累加到进位上carry += a[cur1] - '0';// 指针 cur1 向前移动一位--cur1;}// 如果字符串 b 还未遍历完if (cur2 >= 0) {// 将当前字符转换为数字并累加到进位上carry += b[cur2] - '0';// 指针 cur2 向前移动一位--cur2;}// 将当前位的结果(carry 对 2 取余)转换为字符添加到结果字符串 ret 中ret.push_back(carry % 2 + '0');// 更新进位,carry 除以 2 得到新的进位carry /= 2;}// 由于结果是从低位到高位添加到 ret 中的,需要反转字符串得到正确的顺序reverse(ret.begin(), ret.end());// 返回最终的二进制加法结果return ret;}
};