剑指 Offer II 002. 二进制加法

题目描述

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

输入为非空字符串且只包含数字 1 和 0。

示例?1:

输入: a = "11", b = "10"
输出: "101"
示例?2:

输入: a = "1010", b = "1011"
输出: "10101"
?

提示：

每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。

思路解析

1.这就是大数相加的思路

2.和小时候计算加法一样,从右往左进行竖位相加

3.如果有进位,就加一,如果超过2,那就保留一个进位给下一次用

4.使用StringBuilder进行存储字符串

代码实现

class Solution {
    public String addBinary(String a, String b) {
        if("0".equals(a)&&"0".equals(b)) return "0";
        if("0".equals(a)||"0".equals(b)) return "0".equals(a)?b:a;
        boolean isAdd = false;
        char[] achars = a.toCharArray();
        char[] bchars = b.toCharArray(); 
        int la = achars.length-1;
        int lb = bchars.length-1;
        StringBuilder sb = new StringBuilder();
        while(la>=0&&lb>=0) {
            int ia = achars[la--]-'0';
            int ib = bchars[lb--]-'0';
            int iab = ia+ib;
            if(isAdd) {
                iab++;
                isAdd = false;
            }
            if(iab>=2) {
                iab-=2;
                isAdd = true;
            }
            sb.insert(0,iab);
        }
        while(la>=0) {
            int ia = achars[la--]-'0';
            if(isAdd) {
                ia++;
                isAdd = false;
            }
            if(ia>=2) {
                ia-=2;
                isAdd = true;
            }
            sb.insert(0,ia);
        }
        while(lb>=0) {
            int ib = bchars[lb--]-'0';
            if(isAdd) {
                ib++;
                isAdd = false;
            }
            if(ib>=2) {
                ib-=2;
                isAdd = true;
            }
            sb.insert(0,ib);
        }
        if(isAdd) sb.insert(0,1);
        return sb.toString();
    }
}