「每日LeetCode」2021年8月3日

本文最后更新于：2023年3月19日 晚上

剑指 Offer II 002. 二进制加法

剑指 Offer II 002. 二进制加法

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
输入为 非空  **字符串且只包含数字 1 和 0。
**示例  1:

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

示例  2:

1
2
输入: a = "1010", b = "1011"
输出: "10101"

提示：

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

思路

同字符串十进制加法，每到 2 的时候记录进位即可。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
  let res = "";
  let prev = false;
  const max = Math.max(a.length, b.length);
  a = a.padStart(max, "0");
  b = b.padStart(max, "0");
  for (let i = a.length - 1; i >= 0; i--) {
    const [curA, curB] = [a[i], b[i]];
    let sum = +curA + +curB + (prev ? 1 : 0);
    if (sum >= 2) {
      sum %= 2;
      prev = true;
    } else {
      prev = false;
    }
    res = sum + res;
  }
  return prev ? "1" + res : res;
};