剑指 Offer II 002. 二进制加法

题目

给定两个 01 字符串a和b,请计算它们的和,并以二进制字符串的形式输出。

输入为 非空 字符串且只包含数字1和0。

示例1:
输入: a = “11”, b = “10”
输出: “101”

示例2:
输入: a = “1010”, b = “1011”
输出: “10101”

提示:

  • 每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
  • 1 <= a.length, b.length <= 104
  • 字符串如果不是 “0” ,就都不含前导零。

注意:本题与主站67题重复

题解

public String addBinary(String a, String b) {
    // a、b的长度 a、b和的最大长度
    int len1 = a.length(), len2 = b.length(), max = Integer.max(len1, len2) + 1;
    // 倒叙计算开始索引
    int i = len1 - 1, j = len2 - 1;
    // 二进制和字符位数
    int cnt = 0;
    // 结果字符数组
    char[] result = new char[max];
    // 进位标识
    boolean carry = false;
    
    while (i >= 0 || j >= 0) {
        // 计算相同未计算的最低位
        int t = (i >= 0 ? a.charAt(i) - '0' : 0) + (j >= 0 ? b.charAt(j) - '0' : 0) + (carry ? 1 : 0);
        // 是否需要进位
        carry = t > 1;
        result[max - (cnt++) - 1] = (char) ('0' + (t % 2));
        i--;
        j--;
    }

    // 剩余进位
    if (carry) {
        result[max - (cnt++) - 1] = '1';
    }

    return new String(result, max - cnt, cnt);
}