二进制求和

LeetCode每日一题，67.Add Binary

先看题目描述

大意就是实现二进制加法

算法思路

整体思路是将两个字符串较短的用 00 补齐，使得两个字符串长度一致，然后从末尾进行遍历计算，得到最终结果。还有需要注意的就是要考虑最后是否会多出一位进位

算法源码

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public String addBinary(String a, String b) {
        boolean carry = false;
        Deque<Integer> stack = new LinkedList<>();
        int len1 = a.length();
        int len2 = b.length();
        StringBuffer sb;
        String sa;
        if (len1 >= len2) {
            sb = new StringBuffer(b);
            sa = a;
            while (sb.length() < len1) sb.insert(0, "0");
        } else {
            sb = new StringBuffer(a);
            sa = b;
            while (sb.length() < len2) sb.insert(0, "0");
        }
        int len = sb.length();
        for (int i = 1; i <= len; i++) {
            if (carry) {
                int c = (sa.charAt(len - i) - '0') + (sb.charAt(len - i) - '0') - 1;
                if (c < 0) carry = false;
                stack.push(Math.abs(c));
            } else {
                int c = (sa.charAt(len - i) - '0') + (sb.charAt(len - i) - '0') - 2;
                if (c >= 0) carry = true;
                if (c == -2) c = 0;
                stack.push(Math.abs(c));
            }
        }
        if (carry) stack.push(1);
        StringBuilder res = new StringBuilder();
        while (stack.peek() != null) res.append(String.valueOf(stack.pop()));
        return res.toString();
    }
}

这是一开始自己实现的源码，虽然通过了，整体思路也是一致的，但实现的比较繁琐，下面是看了题解代码后根据此实现的算法源码，代码简洁的多，运行效率也高得多

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