67. 二进制求和

Contents

1. 1. 题目
2. 2. 解题思路
   1. 2.1. 思路1
   2. 2.2. 思路2

题目

给定两个二进制字符串，返回他们的和（用二进制表示）。

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

示例 1:

输入: a = “11”, b = “1”
输出: “100”
示例 2:

输入: a = “1010”, b = “1011”
输出: “10101”

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-binary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

思路1

第一次写这道题，怎么感觉之前做过，字符串二进制进位
使用简单的字符串一个个比较，
第一次问题在字符串拼接，使用insert但没有插入到头部
效率比较低

class Solution {
    public String addBinary(String a, String b) {
        boolean up = false;
        int aLength = a.length();
        int bLength = b.length();
        int strLength = aLength >= bLength ? aLength : bLength;
        if(aLength > bLength){
            b = String.join("", Collections.nCopies(strLength - bLength, "0")) + b;  
        }else if(bLength > aLength){
            a = String.join("", Collections.nCopies(strLength - aLength, "0")) + a;  
        }
        char[] aArray = a.toCharArray();
        char[] bArray = b.toCharArray();
        StringBuilder sb = new StringBuilder();
        for(int i = strLength -1 ; i >= 0 ; i--){
            char aChar = aArray[i];
            char bChar = bArray[i];
            if(aChar == '1' && bChar == '1'){
                if(up){
                    sb.insert(0,"1");
                }else{
                    sb.insert(0,"0");
                }
                up = true;
            }else if(aChar == '0' && bChar == '0'){
                if(up){
                    sb.insert(0,"1");
                }else{
                    sb.insert(0,"0");
                }
                up = false;
            }else{
                if(up){
                    sb.insert(0,"0");
                    up = true;
                }else{
                    sb.insert(0,"1");
                    up = false;
                }
            }
        }
        if(up){
            sb.insert(0,"1");
        }
        return sb.toString();
    }
}

思路2

第二种算法，看别人的答案，思路跟之前相似，但实现不同，不用一堆id判断，用字符与‘0’相减直接得数字
自己写得时候，等于0没有想到

class Solution {
    public String addBinary(String a, String b) {
        int ans = 0;
        StringBuilder sb = new StringBuilder();
        for(int i = a.length()-1 ,j = b.length()-1 ; i>=0 || j>=0 ; i-- ,j--){
            int sum = ans;
            sum += (i >= 0 ? a.charAt(i)- '0' : 0);
            sum += (j >= 0 ? b.charAt(j) - '0': 0);
            sb.append(sum % 2);
            ans = sum /2;
        }
        sb.append(ans == 1? ans : "");
        return sb.reverse().toString();
    }
}