题目出处
题目描述
个人解法
思路：
todo
代码示例：（Java）
todo
复杂度分析
todo
官方解法
题目分析
考虑一个最朴素的方法：先将 a 和 b 转化成十进制数，求和后再转化为二进制数。利用 Python 和 Java 自带的高精度运算，我们可以很简单地写出这个程序：
public class Solution0 {
public String addBinary(String a, String b) {
return Integer.toBinaryString(
Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
);
}
}
如果 a 的位数是 n，b 的位数为 m，这个算法的渐进时间复杂度为 O(n+m)。但是这里非常简单的实现基于 Python 和 Java 本身的高精度功能，在其他的语言中可能并不适用，并且在 Java 中：
- 如果字符串超过 33 位，不能转化为 Integer
- 如果字符串超过 65 位，不能转化为 Long
- 如果字符串超过 500000001 位，不能转化为 BigInteger
因此，为了适用于长度较大的字符串计算，我们应该使用更加健壮的算法。
方法1：模拟
思路：
代码示例：（Java）
public class Solution1 {
public String addBinary(String a, String b) {
StringBuffer ans = new StringBuffer();
int n = Math.max(a.length(), b.length()), carry = 0;
for (int i = 0; i < n; ++i) {
carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
ans.append((char) (carry % 2 + '0'));
carry /= 2;
}
if (carry > 0) {
ans.append('1');
}
ans.reverse();
return ans.toString();
}
}
复杂度分析
方法2:位运算
思路：
代码示例：（Java）
public class Solution2 {
public String addBinary(String a, String b) {
int x = Integer.parseInt(a, 2);
int y = Integer.parseInt(b, 2);
while (y != 0) {
int answer = x ^ y;
int carry = (x & y) << 1;
x = answer;
y = carry;
}
return Integer.toBinaryString(x);
}
}
复杂度分析
考察知识点
1.位运算
