跳至主要內容

67. 二进制求和


67. 二进制求和open in new window

🟢   🔖  位运算 数学 字符串 模拟  🔗 力扣open in new window LeetCodeopen in new window

题目

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 and b consist only of '0' or '1' characters.
  • Each string does not contain leading zeros except for the zero itself.

题目大意

给你两个二进制字符串 ab ,以二进制字符串的形式返回它们的和。

解题思路

这道题和 第 2 题 两数之和 思路相同。

可以设置一个变量 carry 来表示进位,初始时 carry = 0

遍历两个二进制字符串的每一位,从末尾开始逐位相加,并加上进位 carry。将相加的结果和进位的和对 2 取余数,得到当前位的值,对 2 取商,得到进位。将当前位的值插入结果字符串的开头,然后更新进位,继续遍历下一位,直到完成所有位的相加。

最后,若最高位有进位,还需将进位插入结果字符串的开头。

复杂度分析

  • 时间复杂度O(max(m, n)),其中 mn 是字符串 ab 的长度,因为需要逐位遍历两个二进制字符串,长度较长的字符串决定了迭代的次数。
  • 空间复杂度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两数相加open in new window[✓]递归 链表 数学
43字符串相乘open in new window[✓]数学 字符串 模拟
66加一open in new window[✓]数组 数学
989数组形式的整数加法open in new window数组 数学