刷题笔记(2):力扣-67.二进制求和

本题来自 leetcode 题库第 67 题:67.二进制求和,对两个二进制字符串进行求和,难度简单。

题目描述

给你两个二进制字符串,返回它们的和(用二进制表示)。

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

  • 示例 1:

    输入: a = "11", b = "1"

    输出: "100"

  • 示例 2:

    输入: a = "1010", b = "1011"

    输出: "10101"

  • 提示:

    每个字符串仅由字符 '0' 或 '1' 组成。

    1 <= a.length, b.length <= 10^4

    字符串如果不是 "0" ,就都不含前导零。

题解

这题很简单,直接模拟小学时学到的“列竖式”求两数和即可。需要注意以下几点细节:

  1. 两个加数长度不同,将短的加数前面补 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 i = a.length - 1
let j = b.length - 1
let res = ''
let carry = 0
let sum = ''
while (i >= 0 || j >= 0) {
x = i >= 0 ? +a[i] : 0
y = j >= 0 ? +b[j] : 0

sum = carry + x + y
carry = Math.floor(sum / 2)

res = sum % 2 + res

i--, j--
}
return carry ? '1' + res : res
}

该算法时间复杂度为 \(O(n)\),空间复杂度为 \(O(1)\)

当然该题还有其他类似的处理方法或者小技巧,包括根据不同语言特性使用不同的技巧。但整体上的思路应该没有太大差异。

总结与思考

这题比较简单,是一个大数求和的问题。而一些语言本身就提供了大数计算的特性,可以直接使用。以 JavaScriptPython3 为例。

JavaScript 在 stage 4 语法特性中提供了 BigInt 数据类型,专门用于大数计算。使用 BigInt 解题变得十分简洁:

1
2
3
4
5
6
7
8
9
10
/**
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function (a, b) {
a = BigInt('0b' + a)
b = BigInt('0b' + b)
return (a + b).toString(2)
};

而 Python3 默认支持大数运算,只需对结果进行进制转换即可。

1
2
3
class Solution:
def addBinary(self, a: str, b: str) -> str:
return '{0:b}'.format(int(a, 2) + int(b, 2))