二进制字符串相加

问题分析

我们需要将两个二进制字符串相加，并以二进制字符串的形式返回结果。二进制加法的规则类似于十进制加法，只是进位是基于2而不是10。

解决思路

1. 对齐字符串：首先将两个字符串长度对齐，在较短的字符串前面补零，使两个字符串长度相同。
2. 逐位相加：从最低位（字符串的末尾）开始，逐位相加，并处理进位。
3. 处理进位：每一位相加的结果可能有进位，需要在下一位计算时加上进位。
4. 最终进位处理：所有位相加完成后，如果还有进位，需要在结果前面加上一个'1'。

解决代码

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1;
        int carry = 0;
        
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (i >= 0) sum += a.charAt(i--) - '0';
            if (j >= 0) sum += b.charAt(j--) - '0';
            sb.append(sum % 2);
            carry = sum / 2;
        }
        
        if (carry != 0) sb.append(carry);
        return sb.reverse().toString();
    }
}

代码解释

1. 初始化：使用StringBuilder来构建结果字符串，i和j分别指向两个字符串的末尾。

2. 循环相加

   ：只要任一字符串还有未处理的位就继续循环：

   • 计算当前位的和（包括进位）
   • 处理两个字符串当前位的数字
   • 将当前位的结果添加到StringBuilder中
   • 计算新的进位

3. 处理最终进位：如果循环结束后仍有进位，添加到结果中。

4. 反转字符串：因为是从低位开始添加的，所以需要反转得到正确顺序。

复杂度分析

• 时间复杂度：O(max(M,N))，其中M和N是输入字符串的长度。我们需要遍历较长的字符串。
• 空间复杂度：O(max(M,N))，存储结果需要额外的空间。

示例验证

示例1:

输入: a = "11", b = "1"
对齐: a = "11", b = "01"
计算:
  1 + 1 = 0 (进位1)
  1 + 0 + 进位1 = 0 (进位1)
  0 + 0 + 进位1 = 1
结果: "100"

示例2:

输入: a = "1010", b = "1011"
对齐: a = "1010", b = "1011"
计算:
  0 + 1 = 1
  1 + 1 = 0 (进位1)
  0 + 0 + 进位1 = 1
  1 + 1 = 0 (进位1)
  0 + 0 + 进位1 = 1
结果: "10101"

这个解决方案高效地处理了二进制字符串相加的问题，考虑了所有边界情况，包括不同长度的字符串和最终的进位处理。