LeetCode笔记：67. Add Binary

问题：

Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".

大意：

给出两个二进制字符串，返回它们的和（同样是二进制字符串）。
例子：
a = "11"
b = "1"
返回 "100".

思路：

这其实就是一个模拟二进制加法的问题。如果某一位两个数都是0，结果的这一位也为0，有一个1就是1，如果都是1，这一位是0，还有进一位，所以上面三种情况还要考虑低位有没有进位。

因为两个二进制数的长度可能不同，所以我们先要在一个循环中去加两个数的和，当任一个数处理完之后，再看剩下哪个，将其加到结果中去。

这种做法速度还是很快的，只是代码比较多，也可以直接将短的那个加到长的那个上面去，但最后还是要根据进位遍历一遍长的剩余部分，节省不了太多东西。

代码（Java）：

public class Solution {
    public String addBinary(String a, String b) {
        int flag = 0;
        char[] result = new char[a.length() > b.length() ? a.length() : b.length()]; 
        int k = result.length - 1;
        int i = a.length() - 1;
        int j = b.length() - 1;
        for (; i >= 0 && j >= 0; i--, j--, k--) {
            if (a.charAt(i) == '1' && b.charAt(j) == '1') {
                result[k] = flag == 1 ? '1' : '0';
                flag = 1;
            } else if (a.charAt(i) == '1' || b.charAt(j) == '1') {
                result[k] = flag == 1 ? '0' : '1';
                flag = flag == 1 ? 1 : 0;
            } else {
                result[k] = flag == 1 ? '1' : '0';
                flag = 0;
            }
        }
        if (i >= 0) {
            for (; i >=0; i--, k--) {
                if (a.charAt(i) == '1' && flag == 1) {
                    result[k] = '0';
                    flag = 1;
                } else if (a.charAt(i) == '1' || flag == 1) {
                    result[k] = '1';
                    flag = 0;
                } else {
                    result[k] = '0';
                    flag = 0;
                }
            }
        }
        if (j >= 0) {
            for (; j >=0; j--, k--) {
                if (b.charAt(j) == '1' && flag == 1) {
                    result[k] = '0';
                    flag = 1;
                } else if (b.charAt(j) == '1' || flag == 1) {
                    result[k] = '1';
                    flag = 0;
                } else {
                    result[k] = '0';
                    flag = 0;
                }
            }
        }
        return flag == 1 ? "1" + String.valueOf(result) : String.valueOf(result);
    }
}

合集：https://github.com/Cloudox/LeetCode-Record

查看作者首页