LeetCode 67. Add Binary

来源：cnblogs　　作者：flowingfog　　时间：2018/10/20 15:13:00　　对本文有异议

分析

难度易

来源

https://leetcode.com/problems/add-binary/description/

题目

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

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"

Output: "100"

Example 2:

Input: a = "1010", b = "1011"

Output: "10101"

解答

 1 package LeetCode;
 2 
 3 public class L67_AddBinary {
 4     private static String getSum(String a,String b){//a比b长
 5         int len1=a.length();
 6         int len2=b.length();
 7         int[] res=new int[len1+1];//比a多一位，以备进位
 8         StringBuilder str=new StringBuilder();
 9         //StringBuilder res=new StringBuilder();
10         int flag=0;//表示进位
11         //int len=Math.min(len1,len2);//求和部分长度
12         for(int i=0;i<len2;i++){//求和部分长度
13             int aNum=a.charAt(len1-1-i)-'0';//从数字低位，即数组高位起逐位相加
14             int bNum=b.charAt(len2-1-i)-'0';
15             int remainder=(aNum+bNum+flag)%2;
16             res[len1-i]=remainder;
17             flag=(aNum+bNum+flag)/2;
18         }
19         for(int i=0;i<len1-len2;i++){//与b求和后多余部分
20             int aNum=a.charAt(len1-len2-1-i)-'0';//从数字低位，即数组高位起逐位相加
21             int remainder=(aNum+flag)%2;
22             res[len1-len2-i]=remainder;
23             flag=(aNum+flag)/2;
24         }
25         if (flag==1){
26             res[0]=1;
27         }
28         if (flag==1){
29             str.append("1");
30             for(int i=0;i<len1;i++){
31                 str.append(res[i+1]);
32             }
33         }else{
34             for(int i=0;i<len1;i++){
35                 str.append(res[i+1]);
36             }
37         }
38         return str.toString();
39     }
40     public String addBinary(String a, String b) {
41         int len1=a.length();
42         int len2=b.length();
43         if(len1>len2)
44             return getSum(a,b);
45         else
46             return getSum(b,a);
47     }
48 
49     public static void main(String[] args){
50         String a1="11";
51         String b1="1";
52         String a2="100";
53         String b2="110010";
54         L67_AddBinary l67=new L67_AddBinary();
55         System.out.println(l67.addBinary(a2,b2));
56     }
57 }