剑指Offer|LCR 002. 二进制求和

LCR 002. 二进制求和

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "10"
输出: "101"

提示：

• 每个字符串仅由字符 '0' 或 '1' 组成。
• 1 <= a.length, b.length <= 10^4
• 字符串如果不是 "0" ，就都不含前导零。

使用js语言编写代码

法1：转为十进制计算，再转为二进制

分析：

可以将二进制字符转换成int型，然后把两个整数相加，再换成二进制字符。例如：$(11{)}_2+(10{)}_2=(3{)}_{10}+(2{)}_{10}=(5{)}_{10}=(101{)}_2$（下标2表示二进制，10表示十进制）这个解法容易导致溢出。这题没有限制二进制字符串长度。当二进制字符串比较长时，它表示的整数可能超出int型整数或long型整数的范围，此时不能直接将其转换。

function addBinary(a, b) {
    // 将二进制字符串转换为十进制数
    let numA = parseInt(a, 2);
    let numB = parseInt(b, 2);

    // 计算二者的和
    let sum = numA + numB;

    // 将和转换为二进制字符串并返回
    return sum.toString(2);
};

leetcode上通过不了，计算示例 1还可以。

法2：直接加，逢二进一

分析：

按照十进制加法的思想，十进制是逢十进一，二进制是逢二进一。

二进制加法类似，从字符串的右端出发，向左做加法，逢二进一。

以a = "11", b = "10"为例：

定义各自数组的索引，从右端出发计算，所以初始化为i = a.length - 1，j同理。此时获取到数字1和数字0，即digitA=1,digitB=0,sum = 1,加入结果result = '1'

i和j等于0时，digitA=1,digitB=1,sum= 1+1+0 = 2，carry = 1，sum大于等于自减2，sum为0，加入结果result = '01'

当前carry=1，再在结果中加个进位result = '101'

• 时间复杂度：O(max(m, n))
• 空间复杂度：O(max(m, n))

其中，m 是字符串 a 的长度，n 是字符串 b 的长度。

var addBinary = function(a, b) {
    let result = '';
    let i = a.length - 1; // a的索引,从右往左遍历
    let j = b.length - 1; // b的索引
    let carry = 0; // 进位
	
    // 两个索引的值只要有一个是合法的（>=0,表明还有数要算），就要进行计算
    while (i >= 0 || j >= 0) {
        // 三目运算符
        // 下标ij合法，就取最右边的数字digitA、digitB
        // 因为a.charAt(i--)本身是字符串，通过 -'0' 操作 变为整数，i--，索引左移
        let digitA = i >= 0 ? a.charAt(i--) - '0' : 0;
        let digitB = j >= 0 ? b.charAt(j--) - '0' : 0;
        let sum = digitA + digitB + carry; // 计算当前位的和
        carry = sum >= 2 ? 1 : 0; // 逢二进一，sum>=2,carry进位就为1
        sum = sum >= 2 ? sum - 2 : sum; // sum>=2的话，需要自减2。也就是二进制中1+1=10，十进制1+1=2，这里的2-2=0，从而获取二进制结果10右端的0，如果sun就是1，就不用管，直接用1
        result = sum + result;  // 将当前位的计算结果加入结果
    }

    if (carry === 1) {
        result = '1' + result;  // carry进位存在的话，需要加到最左端
    }
    return result;
};