二進制求和-LeetCode（Java實作）

題目描述：

給定兩個二進制字元串，傳回他們的和（用二進制表示）。

輸入為非空字元串且隻包含數字 

1

 和 

。

示例 1:

輸入: a = "1010", b = "1011"
輸出: "10101"
           

示例 2:

輸入: a = "10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101"   
      b =  "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"
輸出: "110111101100010011000101110110100000011101000101011001000011011000001100011110011010010011000000000"
           

解題思路：   如果先把兩個二進制字元串轉換成數字，再求和，最後變成字元串的話，在本題中很容易出現溢出情況。

1. 因為二進制字元串的加和是從右往左計算，是以先反轉兩個二進制字元串（使用StringBuffer提供的方法）。後面的步驟都基于反轉後的字元串進行操作。
2. 建立一個StringBuffer變量用以存放求和後的二進制字元串（後面簡稱為存值字元串）。（使用StringBuffer類，是因為此類的字元串相加操作效率很高）
3. 将兩個字元串變成相同的長度（在短的字元串後面加字元 ‘0’ ，直到兩個字元串長度相同）。
4. 建立一個字元變量來存放需要往後進位的值（flag），初始值為 ‘0’。從左向右，給兩個字元串同一位置的字元以及 flag 進行 ”求和操作“ （滿二進一）。如果求和後，需要向下一位進位，就把需要進位的值，存放在flag中。每次求和操作都要考慮 flag 的值。
5. 完成兩字元串最後一個字元的求和操作後。判斷此時flag的值，如果flag 是 ‘1’，則還需要在存值字元串後面加上 ‘1’；
6. 完成以上操作後，再将存值字元反轉，然後轉換塵為String類，并傳回此。

代碼實作：

class Solution {
    public String addBinary(String a, String b) {
        //反轉字元串
        StringBuffer s1 = new StringBuffer(a);
        s1.reverse();
        StringBuffer s2 = new StringBuffer(b);
        s2.reverse();
        //将兩個字元串變成長度相同。
        if (s1.length() > s2.length()) {
            int n = s1.length() - s2.length();
            for (int i = 0; i < n; i++) {
                s2.append('0');
            }
        }else if (s1.length() < s2.length()) {
            int n = s2.length() - s1.length();
            for (int i = 0; i < n; i++) {
                s1.append('0');
            }
        }
        //進行兩個字元串的求和操作
        StringBuffer stringBuffer = new StringBuffer("");
        int i = 0;
        char flag = '0'; //用來存放進位值的字元變量
        while (i < s1.length() && i < s2.length()) {
            if (flag == '0') {
                if (s1.charAt(i) == s2.charAt(i) && s1.charAt(i) == '1') {
                    flag = '1';
                    stringBuffer.append('0');
                }else if (s1.charAt(i) == s2.charAt(i) && s1.charAt(i) == '0') {
                    stringBuffer.append('0');
                }else {
                    stringBuffer.append('1');
                }
            } else {
                if (s1.charAt(i) == s2.charAt(i) && s1.charAt(i) == '1') {
                    flag = '1';
                    stringBuffer.append('1');
                }else if (s1.charAt(i) == s2.charAt(i) && s1.charAt(i) == '0'){
                    flag = '0';
                    stringBuffer.append('1');
                }else {
                    flag = '1';
                    stringBuffer.append('0');
                }
            }
            i++;
        }
        if (flag == '1') {
            stringBuffer.append(flag);
        }
        stringBuffer.reverse();
        return stringBuffer.toString();
    }
}