原题地址：67. 二进制求和 - 力扣（LeetCode）
题目描述
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
输入:a = "11", b = "1" 输出："100"
示例 2：
输入：a = "1010", b = "1011" 输出："10101"
解题思路
- 创建一个
StringBuffer对象ans来存储最终的结果。 - 确定两个字符串中较长的长度
n，并初始化进位carry为 0。 - 从两个字符串的最低位开始，逐位相加，同时考虑进位。
- 如果当前位在两个字符串的长度范围内，则将其转换为整数并加到
carry上。 - 计算当前位的和（
carry % 2），并将其追加到ans中。 - 更新进位
carry为carry / 2。 - 重复步骤 3-6，直到遍历完所有位。
- 如果最后还有进位（
carry > 0），则将 '1' 追加到ans的开头。 - 将
ans反转，因为结果是从最低位到最高位计算的。 - 返回
ans的字符串表示
源码实现
class Solution {public String addBinary(String a, String b) {// 创建一个 StringBuffer 对象来存储最终结果StringBuffer ans = new StringBuffer();// 确定两个字符串中较长的长度，并初始化进位 carry 为 0int n = Math.max(a.length(), b.length()), carry = 0;for (int i = 0; i < n; ++i) {// 计算 a 中的当前位（如果存在），并加到 carry 上carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;// 计算 b 中的当前位（如果存在），并加到 carry 上carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;// 计算当前位的和，并追加到 ans 中ans.append((char) (carry % 2 + '0'));// 更新进位 carrycarry /= 2;}// 如果最后还有进位，则追加 '1' 到 ans 的开头if (carry > 0) {ans.append('1');}// 反转 ans，因为结果是从最低位到最高位计算的ans.reverse();// 返回 ans 的字符串表示return ans.toString();}
}复杂度分析
-
时间复杂度：O(n)，其中 n 是两个字符串中较长的长度。这是因为我们需要遍历两个字符串的每一位一次。
-
空间复杂度：O(1)，除了输入的字符串外，我们只使用了常数级别的额外空间来存储
StringBuffer对象和进位carry。因此，空间复杂度是常数级别的。