地址
leetcode地址：
难度
简单
题目
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
输入:a = “11”, b = “1”
输出：“100”
示例 2：
输入：a = “1010”, b = “1011”
输出：“10101”
提示：
- 1 <= a.length, b.length <= 10^4
- a 和 b 仅由字符 ‘0’ 或 ‘1’ 组成
- 字符串如果不是 “0” ，就不含前导零
思路
第一个思路就是使用Java自带的API进行。
class Solution {
public String addBinary(String a, String b) {
return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
}
}
写完之后，发现问题。题目中a和b长度最大值为10^4。远远超过了int的数值范围，故不可使用上述的方法。
先回顾下我们十进制加法方式：
首先两个「加数」的右端对齐。
然后从最右侧开始，依次计算对应的两位数字的和。如果和大于等于 10，则把和的个位数字计入结果，并向前面进位。
依次向左计算对应位置两位数字的和，如果有进位需要加上进位。如果和大于等于 10，仍然把和的个位数字计入结果，并向前面进位。
当两个「加数」的每个位置都计算完成，如果最后仍有进位，需要把进位数字保留到计算结果中。
那么二进制加法的计算也可以采用类似的方法。但与十进制不同的是，二进制的进位规则是「逢二进一」，即当求和结果 >=2 时，需要向前进位。
class Solution {
public String addBinary(String a, String b) {
StringBuilder res = new StringBuilder();
int i = a.length() - 1;
int j = b.length() - 1;
int carry = 0;
// a 没遍历完，或 b 没遍历完，或进位不为 0
while (i >= 0 || j >= 0 || carry != 0) {
// 当前 a 的取值
int disA = i >= 0 ? a.charAt(i) - '0' : 0;
// 当前 b 的取值
int disB = j >= 0 ? b.charAt(j) - '0' : 0;
int sum = disA + disB + carry;
// 是否有进位
carry = sum>=2 ? 1 : 0;
// 去除进位后留下的数字
sum = sum>=2 ? sum-2 : sum;
// 把去除进位后留下的数字拼接到结果中
res.append(sum);
i--;
j--;
}
// 把结果反转并返回
return res.reverse().toString();
}
}