leetcode 22.8.1 二进制加法

二进制加法

剑指 Offer II 002. 二进制加法 - 力扣（LeetCode）

未优化解法

public static String addBinary(String a,String b){
    
    //先把两个字符串变成byte数组
    byte[] bytes01 = a.getBytes();
    byte[] bytes02 = b.getBytes();
	//定义两个list
    List<String> al= new ArrayList<String>();
    List<String> bl = new ArrayList<String>();
	//把“0” “1” 转存到list里
    for (int i = 0; i < bytes01.length; i++) {
    
        if (bytes01[i]==48) al.add("0");
        else al.add("1");
    }
    for (int i = 0; i < bytes02.length; i++) {
    
        if (bytes02[i]==48) bl.add("0");
        else bl.add("1");
    }
	//这里把短的二进制数补齐
    int maxSize = 0;
    if (bl.size()>=al.size()){
    
        int turns = bl.size() - al.size();
        maxSize=bl.size();
        for (int i = 0; i < turns; i++) {
    
            al.add(0,"0");
        }
    }else{
    
        int turns = al.size() - bl.size();
        maxSize=al.size();
        for (int i = 0; i < turns; i++) {
    
            bl.add(0,"0");
        }
    }
    String answer="";
    int flag = 0;
    
    //循环模拟二进制加法
    for (int i = 0; i < maxSize; i++) {
    
        int count = Integer.parseInt(al.get(al.size()-1-i))+flag+Integer.parseInt(bl.get(bl.size()-1-i));
        if (count==0) {
    
            answer="0"+answer;
            flag=0;
        }
        if (count==1){
    
            answer="1"+answer;
            flag=0;
        }
        if (count==2){
    
            answer="0"+answer;
            flag=1;
        }
        if (count==3){
    
            answer="1"+answer;
            flag=1;
        }
    }
    if (flag==1) answer="1"+answer;

    return answer;
}

优化后解法

    public static String binaryAdd(String a,String b){
    
        //创建一个字符串构造器
        StringBuilder sb = new StringBuilder();
        //获取字符串长度
        int i = a.length(),j=b.length(),c=0;
        //进行循环，模拟二进制加法
        while(i>0||j>0||c!=0){
    
            int ii = i>0?a.charAt(--i)-'0':0;
            int jj = j>0?b.charAt(--j)-'0':0;
            c=c+ii+jj;
            sb.append(c%2);
            c/=2;
        }
        return sb.reverse().toString();
    }

字符串拼接采用了StringBulider，去掉的补位的操作，也没有用额外的数组和链表；时间复杂度为O(N)，额外空间复杂度为O(1)