67. Add Binary

1.問題

• 給兩個字串, 回傳他們的總和

2.想法

• 提問: 確定是在第一個元素還是最末個元素+ 1

• function header, parameter

• test input

• 說明想法

  • 由於字串的索引是由左到右, 但是bit的排列是由右到左, 因此需要先對input string做reverse, 得到結果後再做一次reverse

• 測試計算複雜度

3.程式碼

class Solution {
public:
    string addBinary(string a, string b) {
        int index = 0, carry = 0, sum = 0, i =0;
        string res = "";
        
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        
        while(index < a.length() && index < b.length()) {
            sum = int(a[index] - '0') + int(b[index] - '0') + carry;
            res.push_back(char((sum % 2) + '0'));
            carry = sum / 2;
            ++index;
        }
        
        if (index < a.length()) {
            for (i = index; i < a.length(); i++) {
                sum = int(a[i] - '0') + carry;
                res.push_back(char((sum % 2) + '0'));
                carry = sum / 2;
            }
        }
        
        if (index < b.length()) {
            for (i = index; i < b.length(); i++) {
                sum = int(b[i] - '0') + carry;
                res.push_back(char((sum % 2) + '0'));
                carry = sum / 2;
            }
        }
        
        if (carry) {
            res.push_back(char(carry + '0'));
        }
        
        reverse(res.begin(), res.end());
        
        return res;
    }
};