地址

leetcode地址：

难度

简单

题目

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入:a = "11", b = "1"

输出："100"

示例 2：

输入：a = "1010", b = "1011"

输出："10101"

提示：

1 <= a.length, b.length <= 10^4a 和 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();    }}