AddBinary [source code]

public class AddBinary {
static
/******************************************************************************/
public class Solution {
    public String addBinary(String a, String b) {
        char[] cha = a.toCharArray(), chb = b.toCharArray();
        int lenA = cha.length, lenB = chb.length;
        int carry = 0; 
        int resLen = Math.max(lenA, lenB);
        char[] res = new char[resLen];
        for (int i = 0; i < resLen; i++) {
            int digitA = lenA - 1 - i >= 0 ? cha[lenA - 1 - i] - '0' : 0;
            int digitB = lenB - 1 - i >= 0 ? chb[lenB - 1 - i] - '0' : 0;
            int sum = digitA + digitB + carry;
            carry = sum / 2;
            res[resLen - 1 - i] = (char) ('0' + sum % 2) ;
        }
        return carry > 0 ? '1' + String.valueOf(res) : String.valueOf(res);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        AddBinary.Solution tester = new AddBinary.Solution();
        String[] inputs = {
            "11", "1",
            "11", "11",
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            String a = inputs[2 * i];
            String b = inputs[1 + 2 * i];
            System.out.println(a + " + " + b + " = " + tester.addBinary(a, b));
        }
    }
}

题目没有明说, 不过给的 ab 两个 string 应该是没有leading0的;
总体来说是一个比较简单的题目, 只要选择好合理的数据结构就行了, 最后的速度是2ms (97%), 意外的好; 看了一下, 好像是最优解了;

char 可以直接 xor, 不需要先转换成 int(反正 domain 是 binary 的就行); 不过这里是用不上, 因为这里反正要考虑 carry;

java> '1' ^ '0'  
java.lang.Integer res0 = 1  
java> '1' ^ '1'  
java.lang.Integer res1 = 0  
java> '0' ^ '0'  
java.lang.Integer res2 = 0

char to int一般不需要 cast, 直接知道取int code, 比如用来做 index 的时候; 但是int to char的时候好像一般还是必须要 cast 一下;

discussion 最优解貌似跟我这个算法的思路差不多;

Problem Description

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Difficulty:Easy
Total Accepted:146K
Total Submissions:455.1K
Contributor: LeetCode
Companies
facebook
Related Topics
math string
Similar Questions
Add Two Numbers Multiply Strings Plus One