67.md

67. 二进制求和

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

思路

• 标签：字符串、二进制
• 按照正常的思路，直接使用二进制相加求和；或者转换为十进制求和后，再转换回二进制
• 直接使用二进制相加，从后往前遍历相加，记录进位最后将结果反转。
• 时间复杂度：O(n)，需要遍历所有元素
• 空间复杂度：O(n)，额外需要长度为 N 的字符串存放结果

a       1 0 1 0
b       1 1 1 1   
       <----从后往前
sumStr        1 0 0 1 1
                反转
              1 1 0 0 1

代码

# Python3
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        sumStr,carry = "",0
        i,j = len(a) - 1,len(b) - 1
        while i >= 0 or j >= 0:
            sum = carry
            if i >= 0: sum += int(a[i])
            if j >= 0: sum += int(b[j])
            sumStr += str(int(sum % 2))
            carry = int(sum / 2)
            i = i - 1
            j = j - 1
        if carry == 1: sumStr += "1"
        return sumStr[::-1] ## 反转 sumStr

// Java
class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sumStr = new StringBuilder();
        int carry = 0;
        for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
            int sum = carry;
            sum += i >= 0 ? a.charAt(i) - '0' : 0; // char 转 int
            sum += j >= 0 ? b.charAt(j) - '0' : 0;
            sumStr.append(sum % 2);
            carry = sum / 2;
        }
        if (carry == 1) sumStr.append("1");
        return sumStr.reverse().toString();
    }
}

Python3 可直接使用内置函数，先转换为 10 进制相加，再转换为 2 进制

# Python3
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return bin(int(a, 2) + int(b, 2))[2:]

• int()，其他类型数据转换为 int，第二个参数为数据的进制
• bin()，将十进制转换为二进制，默认前面有 0b，所以截取第二个字段以后数据

测试用例

输入	输出
"11" "1"	"100"
"1010" "1011"	"10101"
"0" "0"	"0"
"1111" "1111"	"11110"

# Python3
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        if len(a) < len(b):
            a = (len(b) - len(a)) * "0" + a
        if len(b) < len(a): 
            b = (len(a) - len(b)) * "0" + b
        maxLen,carry = max(len(a), len(b)),0
        sumStr = ""
        for i in reversed(range(maxLen)):
            sum = carry
            sum += int(a[i])
            sum += int(b[i])
            sumStr += str(int(sum % 2))
            carry = int(sum / 2)
        if carry == 1: # 如果还有进位，加上进位
            sumStr += "1"
        return sumStr[::-1] ## 反转 sumStr