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

LCR 002. 二进制求和

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

法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进位就为1sum = sum >= 2 ? sum - 2 : sum; // sum>=2的话，需要自减2。也就是二进制中1+1=10，十进制1+1=2，这里的2-2=0，从而获取二进制结果10右端的0，如果sun就是1，就不用管，直接用1result = sum + result;  // 将当前位的计算结果加入结果}if (carry === 1) {result = '1' + result;  // carry进位存在的话，需要加到最左端}return result;
};