题解 | #二进制求和#

二进制求和

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

题意理解

把两个字符串格式的二进制数字相加,求和的结果也用字符串的二进制数表示。

方法一

高精度加法
把字符串二进制数字转换成数组格式,每一位对应于数组中的一个整型元素。两个数组a,b从位置0开始表示二进制数的最低位(即倒序),在每一个位置上做加法操作,并计算是否要进位。当较短的数字的每一位都加完后,单独处理另外一个数组剩下的位。

示意图如下: alt

具体代码如下:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @param B string字符串 
     * @return string字符串
     */
    string binaryAdd(string A, string B) {
        // write code here
        vector<int> a,b,c;
        string s;
        for (int i=A.size()-1;i>=0;i--)
        {
            a.push_back(A[i]-'0');
        }
        for (int i=B.size()-1;i>=0;i--)
        {
            b.push_back(B[i]-'0');
        }
        int i = 0, jinwei = 0;
        while (i<A.size() && i<B.size())
        {
            //计算结果的每一位和进位
            c.push_back((a[i]+b[i]+jinwei)%2);
            jinwei = (a[i]+b[i]+jinwei)/2;
            i++;
        }
        //处理剩余的数字
        if (i==A.size())
        {
            while (i<B.size())
            {
                c.push_back((b[i]+jinwei)%2);
                jinwei = (b[i]+jinwei)/2;
                i++;
            }
        }
        else
        {
            while (i<A.size())
            {
                c.push_back((a[i]+jinwei)%2);
                jinwei = (a[i]+jinwei)/2;
                i++;
            }
        }
        if (jinwei) c.push_back(1);
        for (int j=c.size()-1;j>=0;j--)
        {
            s = s + to_string(c[j]);
        }
        return s;
    }
    
};

时间复杂度: O(N)O(N)。对于字符串A,B和数组a,b都遍历了一遍,长度统一用N表示。
空间复杂度: O(N)O(N)。使用数组a,b,c存储二进制数字,长度均为N。

方法二

异或
使用异或来计算二进制中每一位的加法,当两个数字相同时,异或结果为0;两个数字不同时,异或结果为1。同样的,进位也要加入异或运算。

具体代码如下:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @param B string字符串 
     * @return string字符串
     */
    string binaryAdd(string A, string B) {
        // write code here
        string s;
        int jinwei = 0, i;
        int n = A.size()-1, m = B.size()-1;
        for (i=0;i<=n && i<=m;i++)
        {
            //使用异或进行计算
            s = s + to_string(A[n-i]^B[m-i]^jinwei);
            if ((A[n-i]==B[m-i] && A[n-i]=='1') || (A[n-i]!=B[m-i] && jinwei))
                jinwei = 1;
            else jinwei = 0;
        }
        //处理剩余的位数
        if (i==(n+1))
        {
            while (i<=m)
            {
                s = s + to_string((B[m-i]-'0')^jinwei);
                jinwei = jinwei && (B[m-i]=='1');
                i++;
            }
        }
        else
        {
            while (i<=n)
            {
                s = s + to_string((A[n-i]-'0')^jinwei);
                jinwei = jinwei && (A[n-i]=='1');
                i++;
            }
        }
        if (jinwei) s = s + '1';
        reverse(s.begin(), s.end());
        return s;
    }
    
};

时间复杂度: O(N)O(N)。对于字符串A,B都遍历了一遍,长度统一用N表示。
空间复杂度: O(N)O(N)。使用字符串s存储最后的结果。

全部评论

相关推荐

头像
10-09 19:35
门头沟学院 Java
洛必不可达:java的竞争激烈程度是其他任何岗位的10到20倍
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务