67

Posted on In , Views:

題目:
https://leetcode.com/problems/add-binary/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    string addBinary(string a, string b) {
        if(b.empty()) return a;
        if(a.empty()) return b;
        string result = "";
        int i = a.length()-1; // index
        int j = b.length()-1;
        int carry = 0;

        int sum = 0;
        while(i>=0 || j>=0 || carry){ // 當a或b還沒走到底，或仍然有carry時就繼續
            sum = carry; // 直接讓sum = carry，減少判斷
            if(i >= 0){
                sum += a[i] - '0'; // 取得a[i]的值，i-=1
                --i;
            }
            if(j >= 0){
                sum += b[j] - '0'; // 取得b[j]的值，j-=1
                --j;
            }

            result += (sum % 2) + '0'; // 判斷result後綴加上0或1
            carry = sum / 2; // 判斷是否有進位
        }
        // 我們看string a, b是由右往左，建立result時是由左往右，因此要reverse result
        reverse(result.begin(), result.end());
        return result;
    }
};