67. Add Binary

Leetcode link

题目简介

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */

题目给我们 a、b 两个二进制字符串，要求我们求出他们的和

以二进制字符串的形式返回

解题思路

这其实是一道比特位求和的题，核心需要两个方法：

1. 求和：A ^ B ^ C
2. 求进位：(A & B) | ((A ^ B) & C)

其中 A、B 是需要求和的两个比特位，C 是之前求和的进位

有这两个方法后我们只需要实现一个循环计算即可

Javascript

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
    const maxLen = Math.max(a.length, b.length)
    let carry = 0
    const res = []

    const getSum = (A, B, C) => A ^ B ^ C
    const getCarry = (A, B, C) => (A & B) | ((A ^ B) & C)

    for (let i = 0; i < maxLen; i++) {
        const A = parseInt(a.at(-1 - i) || 0, 10)
        const B = parseInt(b.at(-1 - i) || 0, 10)
        const sum = getSum(A, B, carry)
        res.push(sum)
        carry = getCarry(A, B, carry)
    }

    if (carry) {
        res.push(carry)
    }

    return res.reverse().join('')
};

复杂度分析

时间

O(max(len(a), len(b)))

空间

O(max(len(a), len(b)))