LeetCode每日一题 —— 67. 二进制求和解析

LeetCode 是一个提供算法和编程挑战的平台，非常适合想要提高编程技能的人。其中一道非常经典的题目是「二进制求和」，题目要求给定两个二进制字符串，返回它们的和，也是以二进制字符串的形式。这道题目考察的是对二进制加法的理解和实现，非常适合初学者和进阶者。下面，我们将详细解析这道题目，并提供一个高效的解决方案。

题目描述

力扣 LeetCode67. 二进制求和 - 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。 示例1：
输入：a = "11", b = "1" 输出："100" 示例2：
输入：a = "1010", b = "1011" 输出："10101" 提示：
1 <= a.length, b.length <= 10^4
a 和 b 仅由字符 '0' 或 '1' 组成
字符串如果不是 "0" ，就不含前导零

解题思路

为了解决这个问题，我们可以模拟手工进行二进制加法的过程。具体步骤如下：

1. 初始化两个指针 i 和 j，分别指向字符串 a 和 b 的末尾。
2. 初始化一个变量 carry 来存储进位，初始为 0。
3. 初始化一个空字符串 result，用于存储结果。

4. 当 i 或者 j 大于等于 0，或者 carry 不为 0 时，执行循环：

   • 获取当前位的数字，如果指针已经超出字符串长度，则获取 0。
   • 计算当前位的和：sum = a[i] + b[j] + carry。
   • 更新进位：carry = sum / 2。
   • 将当前位的结果添加到 result 的前面：result = (sum % 2) + result。
   • 移动指针：i--，j--。
5. 返回 result 作为最终结果。

代码实现

下面是使用 Python 实现的代码：

def addBinary(a: str, b: str) -> str:
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    result = ""
    while i >= 0 or j >= 0 or carry:
        sum = carry
        if i >= 0:
            sum += int(a[i])
            i -= 1
        if j >= 0:
            sum += int(b[j])
            j -= 1
        carry = sum // 2
        result = str(sum % 2) + result
    return result

测试案例

让我们用题目中给出的示例来测试一下我们的代码：

print(addBinary("11", "1"))  # 输出: "100"
print(addBinary("1010", "1011"))  # 输出: "10101"

总结

通过这个题目，我们不仅学习了如何进行二进制的加法，还学会了如何用代码来模拟手工计算的过程。这种模拟方法在很多算法问题中都是非常有用的，希望这个解析能够帮助你更好地理解并解决类似的问题。