二进制求和 力扣67

一、题目

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

示例 1：

输入:a = "11", b = "1"
输出："100"

示例 2：

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

提示：

• 1 <= a.length, b.length <= 104
• a 和 b 仅由字符 '0' 或 '1' 组成
• 字符串如果不是 "0" ，就不含前导零

二、思路

        整体思路是将两个字符串较短的用 0 补齐，使得两个字符串长度一致，然后从末尾进行遍历计算，得到最终结果。

        初始化变量：
                i 和 j 分别指向字符串 a 和 b 的末尾。
                carry 表示进位，初始值为 0。
                使用 StringBuilder 来构建结果字符串。
        逐位相加：
                如果当前位存在（即索引 i 或 j 大于等于 0），则将其转换为整数（通过减去字符 '0'）。
                将当前位的值与进位相加，得到总和 sum。
                计算新的进位值 carry = sum / 2。
                将当前位的结果（sum % 2）追加到 StringBuilder 中。
        处理剩余的进位：
                如果最终仍有进位（carry != 0），将其追加到结果中。
        反转结果：
                因为是从低位到高位依次计算的，所以需要将结果反转后返回。

下面给出a = "11", b = "1" 的运行过程 ：

三、代码

class Solution {
    public String addBinary(String a, String b) {
        //整体思路是将从后往前一起遍历，如果短的字符串遍历完就在前面补0对齐
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;  //进位
         StringBuilder builder = new StringBuilder();
         while(i >= 0 || j >=0) {  //有一个字符串没遍历完即可
            int digitA = (i >= 0 ? a.charAt(i) - '0': 0); //短的字符串遍历完就在前面补0对齐
            int digitB = (j >= 0 ? b.charAt(j) - '0' : 0);
            int sum = digitA + digitB + carry;
            carry = sum / 2;  //获取进位,很妙
            builder.append( sum % 2); //获取该位数字
            i--;
            j--;
         }
        if(carry != 0) {         //还有进位要处理 比如 11 + 1 = 100  100 中的1
            builder.append(carry);
        }

        return builder.reverse().toString(); //反转
    }
}