67. 二进制求和
67. 二进制求和
🟢 🔖 位运算
数学
字符串
模拟
🔗 力扣
LeetCode
题目
Given two binary strings a
and b
, return their sum as a binary string.
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
Constraints:
1 <= a.length, b.length <= 10^4
a
andb
consist only of'0'
or'1'
characters.- Each string does not contain leading zeros except for the zero itself.
题目大意
给你两个二进制字符串 a
和 b
,以二进制字符串的形式返回它们的和。
解题思路
这道题和 第 2 题 两数之和 思路相同。
可以设置一个变量 carry
来表示进位,初始时 carry = 0
。
遍历两个二进制字符串的每一位,从末尾开始逐位相加,并加上进位 carry
。将相加的结果和进位的和对 2
取余数,得到当前位的值,对 2
取商,得到进位。将当前位的值插入结果字符串的开头,然后更新进位,继续遍历下一位,直到完成所有位的相加。
最后,若最高位有进位,还需将进位插入结果字符串的开头。
复杂度分析
- 时间复杂度:
O(max(m, n))
,其中m
和n
是字符串a
和b
的长度,因为需要逐位遍历两个二进制字符串,长度较长的字符串决定了迭代的次数。 - 空间复杂度:
O(max(m, n))
,res
字符串会存储最终的结果,其最大长度为Math.max(m, n) + 1
(在最坏情况下需要存储进位的额外位数)
代码
/**
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function (a, b) {
// res 存储结果,carry 记录进位
let m = a.length,
n = b.length,
res = '',
carry = 0,
i = 0;
// 模拟加法逻辑
while (i < Math.max(m, n)) {
let num = carry;
num += Number(a[m - i - 1] || 0) + Number(b[n - i - 1] || 0);
res = (num % 2) + res;
carry = Math.floor(num / 2);
i++;
}
return carry ? carry + res : res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
2 | 两数相加 | [✓] | 递归 链表 数学 | |
43 | 字符串相乘 | [✓] | 数学 字符串 模拟 | |
66 | 加一 | [✓] | 数组 数学 | |
989 | 数组形式的整数加法 | 数组 数学 |