LeetCode --- 字符串、數(shù)組
簡(jiǎn)書專欄：http://www.itdecent.cn/nb/41796568
知乎專欄：https://zhuanlan.zhihu.com/c_174823416

一、題目描述

來(lái)源：力扣（LeetCode）
給定兩個(gè)二進(jìn)制字符串，返回他們的和（用二進(jìn)制表示）。
輸入為非空字符串且只包含數(shù)字 1 和 0。

示例:
輸入: a = "11", b = "1"
輸出: "100"

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

二、實(shí)現(xiàn)思路以及代碼

• 首先明確兩個(gè)數(shù)相加，是從后往前加，那么可以定義兩個(gè)指針i,j從后向前遍歷，直到其中一個(gè)小于0的時(shí)候結(jié)束循環(huán)。相加的關(guān)鍵是在于處理進(jìn)位的問(wèn)題。
• 單獨(dú)定義一個(gè)變量up來(lái)控制，當(dāng)兩數(shù)之和加上up大于1時(shí)，表明需要向后進(jìn)位，向結(jié)果字符串的首位置插入當(dāng)前總和減去2（因因?yàn)榭偤痛笥?，說(shuō)明可能是1+1+1或1+1+0的形式，減去2之后即為進(jìn)位之后留在此處的數(shù)字）。
• 否則表明不需要進(jìn)位，直接在字符串首位插入該總和。
• 結(jié)合代碼加以理解

  public static String addBinary(String a, String b) {
        int i = a.length() - 1;
        int j = b.length() - 1;

        StringBuffer br = new StringBuffer();
        //定義進(jìn)位變量
        int up = 0;
        //定義相加之和
        int sum = 0;
        //注意這里用的是或，不是且，因?yàn)槿绻麅蓚€(gè)字符串長(zhǎng)度不一致，剩余的也要加上去
        while (i >= 0 || j >= 0) {
            //上次的進(jìn)位作為本次sum的初始值
            sum = up;
            if (i >= 0) {
                sum += a.charAt(i) - '0';
                i--;
            }
            if (j >= 0) {
                sum += b.charAt(j) - '0';
                j--;
            }

            if (sum > 1) {
                up = 1;
                sum -= 2;
            } else {
                up = 0;
            }
            br.insert(0, sum);
        }

        //最后一位進(jìn)位要加上
        if (up == 1) {
            br.insert(0, 1);
        }
        return br.toString();
    }

更為簡(jiǎn)潔的代碼：

public String addBinary(String a, String b) {
        StringBuffer sb = new StringBuffer();
        int i = a.length() - 1, j = b.length() - 1;
        int carry = 0;
        while(i >= 0 || j >=0) {
            int ta = i >= 0 ? (a.charAt(i) - '0') : 0;
            int tb = j >= 0 ? (b.charAt(j) - '0') : 0;
            int sum = ta + tb + carry;
            carry = sum / 2;
            sum = sum % 2;
            sb.append(sum);
            i--;
            j--;
        }
        if(carry == 1) {
            sb.append("1");
        }
        return sb.reverse().toString();
    }

三、測(cè)試代碼

public static void main(String[] args) {
        String a = "11";
        String b = "1";
        System.out.println(addBinary(a, b));

        a = "1101";
        b = "11";
        System.out.println(addBinary(a, b));
    }

輸出結(jié)果為：

100
10000