题解 | #二进制求和#

题意整理

• 给定两个用字符串表示的二进制数。
• 求它们的和，同样以字符串形式返回。

方法一（模拟竖式计算）

1.思路整理

• 模拟这两个数竖式计算的过程。
• 逐次从低位到高位相加，逢二进一，每次将当前位加入到结果，同时记录余数。
• 最后将结果反转之后返回。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @param B string字符串 
     * @return string字符串
     */
    public String binaryAdd (String A, String B) {
        int m=A.length()-1;
        int n=B.length()-1;
        //进位
        int carry=0;
        StringBuilder sb=new StringBuilder();
        //只要A字符串没加完、或B字符串没加完、或进位不为0，则继续
        while(m>=0||n>=0||carry!=0){
            //A字符串当前字符对应数字
            int t1=(m<0?'0':A.charAt(m--))-'0';
            //B字符串当前字符对应数字
            int t2=(n<0?'0':B.charAt(n--))-'0';
            //求和
            int sum=t1+t2+carry;
            //得到进位
            carry=sum/2;
            //添加当前位
            sb.append(sum%2);
        }                
        return sb.reverse().toString();
    }
}

3.复杂度分析

• 时间复杂度：假设A、B字符串的长度分别为m和n，最多需要计算$max(m,n)+1max(m,n)+1$次，所以时间复杂度为$O(max(m,n))O(max(m,n))$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度是$O(1)O(1)$。

方法二（BigDecimal）

1.思路整理

• 先将A、B字符串转换为十进制的BigDecimal形式。
• 然后计算两者相加的结果，转化为二进制字符串形式返回。

2.代码实现

import java.util.*;
import java.math.BigInteger;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @param B string字符串 
     * @return string字符串
     */
    public String binaryAdd (String A, String B) {
        //将A、B转化为十进制的BigDecimal形式
        BigInteger a = new BigInteger(A,2);
        BigInteger b = new BigInteger(B,2); 
        
        //相加后，再转化为二进制字符串形式
        return (a.add(b)).toString(2);
    }
}

3.复杂度分析

• 时间复杂度：BigDecimal进制转换的复杂度为$lo{g}_{2}nlog\_2n$，n为对应数字的长度，另外只需一次相加操作，假设A、B字符串的长度分别为m和n，则时间复杂度为$O(lo{g}_{2}m\ast n)O(log\_2\{m*n\})$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度是$O(1)O(1)$。