README.md

剑指 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 <= 10^4
• 字符串如果不是 "0" ，就都不含前导零。

 

注意：本题与主站 67 题相同：https://leetcode.cn/problems/add-binary/

解法

模拟笔算加法的过程，注意进位

Python3

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        x, y = len(a) - 1, len(b) - 1
        arr = []
        carry = 0
        while x >= 0 or y >= 0:
            if x >= 0:
                if a[x] == '1':
                    carry += 1
                x -= 1
            if y >= 0:
                if b[y] == '1':
                    carry += 1
                y -= 1
            arr.append(chr((carry & 1) + ord('0')))
            carry >>= 1
        if carry == 1:
            arr.append('1')
        return ''.join(reversed(arr))

Java

class Solution {
    public String addBinary(String a, String b) {
        int x = a.length() - 1, y = b.length() - 1;
        StringBuilder builder = new StringBuilder();
        int carry = 0;
        while (x >= 0 || y >= 0) {
            if (x >= 0) {
                if (a.charAt(x) == '1') {
                    carry += 1;
                }
                x--;
            }
            if (y >= 0) {
                if (b.charAt(y) == '1') {
                    carry += 1;
                }
                y--;
            }
            builder.append((char) ((carry & 1) + '0'));
            carry >>= 1;
        }
        if (carry == 1) {
            builder.append('1');
        }
        return builder.reverse().toString();
    }
}

Go

func addBinary(a string, b string) string {
	x, y := len(a)-1, len(b)-1
	var builder strings.Builder
	carry := 0
	for x >= 0 || y >= 0 {
		if x >= 0 {
			if a[x] == '1' {
				carry += 1
			}
			x--
		}
		if y >= 0 {
			if b[y] == '1' {
				carry += 1
			}
			y--
		}
		builder.WriteRune(rune(carry&1 + '0'))
		carry >>= 1
	}
	if carry == 1 {
		builder.WriteRune('1')
	}
	bytes := []byte(builder.String())
	for i, j := 0, len(bytes)-1; i < j; i, j = i+1, j-1 {
		bytes[i], bytes[j] = bytes[j], bytes[i]
	}
	return string(bytes)
}

C++

class Solution {
public:
    string addBinary(string a, string b) {
        string res;
        int carry = 0;

        int i = a.size() - 1;
        int j = b.size() - 1;

        while (i >= 0 || j >= 0) {
            int digitA = i >= 0 ? a.at(i--) - '0' : 0;
            int digitB = j >= 0 ? b.at(j--) - '0' : 0;
            int sum = digitA + digitB + carry;
            carry = sum >= 2 ? 1 : 0;
            sum = sum >= 2 ? sum - 2 : sum;
            res += to_string(sum);
        }

        if (carry == 1) res.push_back('1');
        reverse(res.begin(), res.end());
        return res;
    }
};

...