Add Binary

Apr 12, 2016


Add Binary

题目描述

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

For example,

a = "11"

b = "1"

Return "100".

解法

代码如下:

public static String addBinary( String a, String b ) {
    StringBuilder sb = new StringBuilder();
    int carry = 0;
    for( int i = a.length()-1, j = b.length()-1; i >= 0 || j >= 0; --i, --j ) {
        int val1 = i >= 0 ? a.charAt(i)-'0' : 0;
        int val2 = j >= 0 ? b.charAt(j)-'0' : 0;
        int sum = val1 + val2 + carry;
        carry = sum / 2;
        sb.append( (char)( (sum%2) + '0' ) );
    }
    if( carry != 0 )
        sb.append( (char)( carry + '0' ) );
    return sb.reverse().toString();
}

思考过程: 处理过程与这里相似, 重点在于学习代码的简洁性.

时空复杂度: 时间复杂度是O(n), 空间复杂度是O(1)


上一篇博客:Valid Anagram
下一篇博客:Single Number(II)(III)