题解 | #二进制求和#

二进制求和

题目描述 给定两个用字符串表示的二进制数，返回他们的和。

方法一：模拟加法

解题思路

对于本题，采用模拟的方法进行求解，即对齐两个字符串，然后对应相加即可。

解题代码

class Solution {
public:
    string binaryAdd(string A, string B) {
        string r = "";
        int digit = 0;// 进位
        for(int i = 0; i < max(A.length(),B.length()); i++)
        {
            if(i < A.length())digit += A[A.length()-1-i] - '0'; // A的低i位
            if(i < B.length())digit += B[B.length()-1-i] - '0'; // B的低i位
            r = string("") + char(digit%2 + '0') + r; // 拼接结果
            digit /= 2; // 进位
        }
        while(digit)
        { // 超出了原本的位数
            r = string("") + char(digit%2 + '0') + r; // 拼接结果
            digit /=2; // 进位
        }
        return r; // 返回结果
    }
};

复杂度分析

时间复杂度：一层循环，因此时间复杂度为$O(n)O(n)$。

空间复杂度：使用字符串r来保存结果，因此空间复杂度为$O(n)O(n)$。

方法二：调库的方法

解题思路

使用python自带的高精度库进行求解。

解题代码

class Solution:
    def binaryAdd(self , A: str, B: str) -> str:
        return format(int(A,2)+int(B,2),"b")

复杂度分析

时间复杂度：数字和字符串之间进行转换以及加法运算，因此时间复杂度为$O(n)O(n)$。

空间复杂度：数字和字符串之间进行转换，消耗内存地址空间，因此空间复杂度为$O(n)O(n)$。