题解 | #二进制求和#

二进制求和

http://www.nowcoder.com/practice/1620262056c24c0e96de32fb261703d0

二进制求和

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

方法一:模拟加法

解题思路

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

alt

解题代码

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)

算法 文章被收录于专栏

算法题的题解以及感受

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务