你好,游客 登录
背景:
阅读新闻

【leetcode】Add Binary - IT-Homer 专栏

[日期:2013-04-13] 来源:  作者: [字体: ]

Question:

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Anwser 1:      

class Solution {
public:
    string addBinary(string a, string b) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        string sum = "";
        int alen = a.length() - 1;
        int blen = b.length() - 1;
        int carry = 0;
        while (alen >= 0 || blen >= 0 || carry > 0) {
            int v = carry;
            if (alen >= 0) v += a[alen] - '0';
            if (blen >= 0) v += b[blen] - '0';

            carry = v / 2;
            sum = string(1, ( '0' + (v&1) ) ) + sum; 
            alen--;
            blen--;
        }
        return sum;
    }
};


Anwser 2:      wrong for large and large binary string, such as a = "111111111111111111111111000000000000000000000000000000000000000000111111111" 

class Solution {
public:
    int str2num(string str){
        int len = str.length();
        if(len <= 0) return 0;
        
        int sum = 0;
        int base = 2;
        int pow = 1;
        
        for(int i = 1; i <= len; i++){
            int val = str[len - i] - '0';
            if(i == 1){
                sum += val;
            } else {
                pow *= base;
                sum += val * pow;
            }
        }
        return sum;
    }
    
    string num2str(int num){
        if(num == 0 ) return "0";
        
        string str = "";
        
        int mod = num % 2;
        do{
            str = string(1, mod + '0') + str;
            num = num / 2;
            mod = num % 2;
        } while (num > 0);
        
        return str;
    }
    
    string addBinary(string a, string b) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return num2str( str2num(a) + str2num(b) );
    }
};
注意点:

1) 思路是将binary先转化成整数(int, long, ulong, long long等),然后相加(a + b),最后再将整数和转化回binary字符串

2) 对小数据,此方法可行(Judge Small is ok); 但对大数据,此方法溢出(Judge Large is wrong)

3) 此算法,可以引申为大整数计算问题(大整数加、减、乘、除)






收藏 推荐 打印 | 录入:admin | 阅读:
相关新闻