天天看點

二進制求和-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();
    }
}