LeetCode之二进制求和

75 阅读 0 评论 50 点赞

我是靠谱客的博主温暖指甲油，最近开发中收集的这篇文章主要介绍LeetCode之二进制求和，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

**题目：**给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
示例：
在这里插入图片描述题目解析：
方法一：利用API完成操作
思路：考虑一个最朴素的方法：先将 aa 和 bb 转化成十进制数，求和后再转化为二进制数。利用 Python 和 Java 自带的高精度运算，我们可以很简单地写出这个程序

class Solution {
    public String addBinary(String a, String b) {
        return Integer.toBinaryString(
            Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
        );
    }
}

分析：
如果 aa 的位数是 nn，bb 的位数为 mm，这个算法的渐进时间复杂度为 O(n + m)O(n+m)。但是这里非常简单的实现基于 Python 和 Java 本身的高精度功能，在其他的语言中可能并不适用，并且在 Java 中：
- 如果字符串超过 3333 位，不能转化为 Integer
- 如果字符串超过 6565 位，不能转化为 Long
- 如果字符串超过 500000001500000001 位，不能转化为 BigInteger
因此，为了适用于长度较大的字符串计算，我们应该使用更加健壮的算法。

方法二：模拟
思路与算法：
在这里插入图片描述

class Solution {
    public String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();

        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0'));
            carry /= 2;
        }

        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();

        return ans.toString();
    }
}

复杂度分析
假设 n=max{∣a∣,∣b∣}。
时间复杂度：O(n)，这里的时间复杂度来源于顺序遍历 a 和 b。
空间复杂度：O(1)，除去答案所占用的空间，这里使用了常数个临时变量

方法三
如果不允许使用加减乘除，则可以使用位运算替代上述运算中的一些加减乘除的操作。

如果不了解位运算，可以先了解位运算并尝试练习以下题目：

只出现一次的数字 II
只出现一次的数字 IIl
数组中两个数的最大异或值
重复的DNA序列
最大单词长度乘积
我们可以设计这样的算法来计算：

把 aa 和 bb 转换成整型数字 x 和 y，在接下来的过程中，x 保存结果，y 保存进位。
当进位不为 0 时
- 计算当前 x 和 y 的无进位相加结果：answer = x ^ y
- 计算当前 x 和 y 的进位：carry = (x & y) << 1
- 完成本次循环，更新 x = answer，y = carry
返回 x 的二进制形式
为什么这个方法是可行的呢？在第一轮计算中，answer 的最后一位是 x 和 y 相加之后的结果，carry 的倒数第二位是 x 和 y 最后一位相加的进位。接着每一轮中，由于 carry 是由 x 和 y 按位与并且左移得到的，那么最后会补零，所以在下面计算的过程中后面的数位不受影响，而每一轮都可以得到一个低 i 位的答案和它向低 i + 1位的进位，也就模拟了加法的过程。

class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            answer = x ^ y
            carry = (x & y) << 1
            x, y = answer, carry
        return bin(x)[2:]