【JAVA算法】简单-二进制求和

算法虽难,循序渐进,督促自己,总有进步;
本博文仅为了督促自己学习算法,如有遗漏或错误之处,请不吝指教;

题目

给定两个二进制字符串,返回他们的和(用二进制表示)。
输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

解题方案:

1.使用JAVA API简单方法

算法思路

  • 通过API Integer.parseInt(a, 2) 将 a 和 b 转换为十进制整数
  • 将a和b得到的十进制整数相加求和
  • 通过Integer.toBinaryString()方法将十进制整数转换为二进制字符串

JAVA代码

class Solution {
  public String addBinary(String a, String b) {
    return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
  }
}

复杂度

算法的时间复杂度为 O(N+M)

存在问题

但是该方法存在问题:

  • 33 位 1,不能转换为 Integer
  • 65 位 1,不能转换为 Long
  • 500000001 位 1,不能转换为 BigInteger

解决办法

为了适用于长度较大的字符串计算,将介绍下面两只哦那个方法:

  • 逐比特位的计算方法
  • 位操作计算方法

2.逐位计算

算法思路

  • 将二进制字符串a和b,从最低位(末尾)向最高位逐位相加
  • 定义初始进位carry=0,如果数a 的最低位是 1,则进位carry加1,同理如果b最低位是 1,则进位carry加1
  • 判断carry是否=2,如果是StringBuilder追加0,否则追加1
  • 最后需要额外判断进位carry是否=1,如果是StringBuilder追加1
  • 最后反转字符串得到正确的结果

JAVA代码

class Solution {
    public String addBinary(String a, String b) {
        int m = a.length(), n = b.length();
        if(m < n) return addBinary(b,a);
        int carry = 0,j = n-1;
        StringBuilder sb = new StringBuilder();
        for(int i=m-1;i>-1;i--){
            if(a.charAt(i) == '1') ++carry;
            if(j > -1 && b.charAt(j--) == '1') ++carry;
            sb.append(carry % 2 == 1 ? "1" : "0");
            carry /= 2;
        }
        if(carry > 0) sb.append("1");
        sb.reverse();
        return sb.toString();
    }
}

复杂度

  • 时间复杂度:O(max(N,M)),其中 N 和 M 是输入字符串 a 和 b 的长度。
  • 空间复杂度:O(max(N,M)),存储求和结果。

存在问题

如果输入的数字很大,该方法的效率非常低

解决办法

  • 使用位操作提高计算速度

2.位操作

算法思路

1.XOR 操作得到两个数字无进位的相加结果
2.AND操作后左移1位操作得到进位carry二进制结果
【JAVA算法】简单-二进制求和_第1张图片
现在问题被简化为:

  • 首先计算两个数字的无进位相加结果和进位
  • 然后计算无进位相加结果与进位之和。同理求和问题又可以转换成上一步,直到进位为 0 结束

JAVA代码

import java.math.BigInteger;
class Solution {
    public String addBinary(String a, String b) {
        BigInteger ab = new BigInteger(a,2);
        BigInteger bb = new BigInteger(b,2);
        BigInteger zero = new BigInteger("0",2);
        BigInteger addWithOutCarry,carry;
        while(bb.compareTo(zero) != 0){
            addWithOutCarry = ab.xor(bb);
            carry = ab.and(bb).shiftLeft(1);
            ab = addWithOutCarry;
            bb = carry;
        }
        return ab.toString(2);
    }
}

复杂度

  • 时间复杂度:O(N+M),其中 N 和 M 是输入字符串 aa 和 bb 的长度。
  • 空间复杂度:O(max(N,M)),存储计算结果。

性能分析

  • 如果输入数字大于 2的100次方,必须使用效率较低的 BigInteger
  • 在 Java 中,应当首先考虑使用 Integer 或者 Long,而不是 BigInteger

欢迎关注我的公众号,每日更新,督促自己进步

你可能感兴趣的