• 作者： 负雪明烛
• id： fuxuemingzhu
• 个人博客： http://fuxuemingzhu.cn/
• 公众号：负雪明烛
• 本文关键词：Leetcode, 力扣，加法，两数之和，求加法，二进制加法，Python, C++, Java

[LeetCode]

题目地址：https://leetcode-cn.com/problems/JFETK5/

题目描述

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

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

示例 1:

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

示例 2:

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

提示：

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

题目大意

给出了一个数组表示的十进制数字，数组的每个位置都是单个数字，现在要把这个十进制数字+1，求结果数组。

解题方法

大家好，我是 @负雪明烛。
​

「求加法」是个系列题目，类似的题目见文末。

解题方法：模拟法

十进制加法

我们先回顾一下十进制加法的计算过程，红点表示进位：

使用「竖式」计算十进制的加法的方式：

1. 两个「加数」的右端对齐；
2. 从最右侧开始，依次计算对应的两位数字的和。如果和大于等于 10，则把和的个位数字计入结果，并向前面进位。
3. 依次向左计算对应位置两位数字的和，如果有进位需要加上进位。如果和大于等于 10，仍然把和的个位数字计入结果，并向前面进位。
4. 当两个「加数」的每个位置都计算完成，如果最后仍有进位，需要把进位数字保留到计算结果中。

二进制加法

二进制加法的计算也可以采用类似的方法，与十进制不同的是，二进制的进位规则是「逢二进一」，即当求和结果 $>=2$ 时，需要向前进位。

• 红点表示进位。

代码

在代码中需要注意的有：

1. 本题给出的二进制数字是字符串形式，不可以转化成 int 型，因为可能溢出；
2. 两个「加数」的字符串长度可能不同；
3. 在最后，如果进位 carry 不为 0，那么最后需要计算进位；
4. 向结果字符串 res 拼接的顺序是向后拼接，返回时需要把 res 反转 。

代码中的巧妙之处：

1. while (i >= 0 || j >= 0 || carry != 0)含义：
   • 字符串 a 和 b 只要有一个没遍历完，那么就继续遍历；
   • 如果字符串 a 和 b 都遍历完了，但是最后留下的进位 carry != 0，那么需要把进位也保留到结果中。
2. 取 digit 的时候，如果字符串 a 和 b 中有一个已经遍历完了（即 $i<=0$ 或者 $j<=0$），则认为 a 和 b 的对应位置是 $0$ 。

Java 代码如下，有详细的注释：

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder(); // 返回结果
        int i = a.length() - 1; // 标记遍历到 a 的位置
        int j = b.length() - 1; // 标记遍历到 b 的位置
        int carry = 0; // 进位
        while (i >= 0 || j >= 0 || carry != 0) { // a 没遍历完，或 b 没遍历完，或进位不为 0
            int digitA = i >= 0 ? a.charAt(i) - '0' : 0; // 当前 a 的取值
            int digitB = j >= 0 ? b.charAt(j) - '0' : 0; // 当前 b 的取值
            int sum = digitA + digitB + carry; // 当前位置相加的结果
            carry = sum >= 2 ? 1 : 0; // 是否有进位
            sum = sum >= 2 ? sum - 2 : sum; // 去除进位后留下的数字
            res.append(sum); // 把去除进位后留下的数字拼接到结果中
            i --;  // 遍历到 a 的位置向左移动
            j --;  // 遍历到 b 的位置向左移动
        }
        return res.reverse().toString(); // 把结果反转并返回
    }
}

C++ 代码如下：

class Solution {
public:
    string addBinary(string a, string b) {
        string res;
        int carry = 0;
        int i = a.size() - 1;
        int j = b.size() - 1;
        while (i >= 0 || j >= 0 || carry != 0) {
            int digitA = i >= 0 ? a[i] - '0' : 0;
            int digitB = j >= 0 ? b[j] - '0' : 0;
            int sum = digitA + digitB + carry;
            carry = sum >= 2 ? 1 : 0;
            sum = sum >= 2 ? sum - 2 : sum;
            res += to_string(sum);
            i --;
            j --;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

Python 代码如下：

class Solution(object):
    def addBinary(self, a, b):
        res = ""
        carry = 0
        i = len(a) - 1
        j = len(b) - 1
        while i >= 0 or j >= 0 or carry != 0:
            digitA = int(a[i]) if i >= 0 else 0
            digitB = int(b[j]) if j >= 0 else 0
            sum = digitA + digitB + carry
            carry = 1 if sum >= 2 else 0
            sum = sum - 2 if sum >= 2 else sum
            res += str(sum)
            i -= 1
            j -= 1
        return res[::-1]

复杂度分析：

• 时间复杂度：$O(max(M,N))$，$M$ 和 $N$ 分别是字符串 a 和 b 的长度；
• 空间复杂度：$O(1)$，只使用了常数的空间。

类似题目

看完本题解，你可以解决以下题目：

• 2. 两数相加
• 445. 两数相加 II
• 67. 二进制求和
• 415. 字符串相加
• 66. 加一
• 989. 数组形式的整数加法

总结

1. 「加法」系列题目都不难，其实就是 「列竖式」模拟法。
2. 需要注意的是 while循环结束条件，注意遍历两个「加数」不要越界，以及进位。

日期

2016 年 05月 8日
2018 年 11 月 21 日 —— 又是一个美好的开始
2021 年 11 月 3 日 —— 持续学习！

最后

以上就是从容玫瑰为你收集整理的剑指 Offer II 002. 二进制加法题目描述题目大意解题方法类似题目总结日期的全部内容，希望文章能够帮你解决剑指 Offer II 002. 二进制加法题目描述题目大意解题方法类似题目总结日期所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。