Add Binary, Leetcode 解题笔记

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

For example,
a = “11”
b = “1”
Return “100”.

这道题思路比较简单,主要考察3个知识点:
1. String的基本处理,类似这样的加合问题,通常先把String反转会比较容易处理,最后记得把结果再反转回来。
2. char to int 和 int to char的转换: 这里既可以使用下面code中的method,如果不熟悉或记不住,也可以char c = (char)(1 + ‘0’); 或者反过来 int i = (int)(‘1’ – ‘0’); 注意前面的显性转化是必须的,不然返回的不是我们想得到的数字或字符,而是ASCII码的对应值。
3. 进位的处理和开头0的处理

public class Solution {
    public String addBinary(String a, String b) {
        String ar = new StringBuilder(a).reverse().toString();
        String br = new StringBuilder(b).reverse().toString();
        StringBuilder ret = new StringBuilder();
        int i = 0;
        int carry = 0;
        int value = 0;

        while(i < Math.min(a.length(), b.length())){
            value = (Character.getNumericValue(ar.charAt(i))) + (Character.getNumericValue(br.charAt(i))) + carry;
            ret.append(value%2);
            carry = value / 2;
            i++;
        }
        
        while(i < a.length()){
            value = (Character.getNumericValue(ar.charAt(i))) + carry;
            ret.append(value%2);
            carry = value / 2;
            i++;
        }

        while(i < b.length()){
            value = (Character.getNumericValue(br.charAt(i))) + carry;
            ret.append(value%2);
            carry = value / 2;
            i++;
        }
        
        //处理最前面一位的进位问题
        if(carry == 1){
            ret.append('1');
        }

        //处理开头为0的问题
        int j = ret.length()-1;
        while(j > 0){
            if(ret.charAt(j) == '0'){
                ret.deleteCharAt(j);
                j--;
            }
            else{
                break;
            }
        }

        return ret.reverse().toString();
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s