leetcode刷题n21-q67：二进制求和

这是我参与11月更文挑战的第23天，活动详情查看：2021最后一次更文挑战

题目描述

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

 

示例 1:

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

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

提示：

每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-binary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
复制代码

思路 & CODE

1. 模拟

两个二进制数相加难点就在于如何处理进位，如果不考虑时空问题，慢慢写这道题目，就像写一个故事一样流畅。

末尾对齐，逐位相加

既然要把两个字符从末尾对其进行相加，那么就要考虑到两个字符长短不一致的问题，所以算法开始就找出最长的字符，遍历这个字符，较短的字符没有值时，就用0补足。

两个二进制数进行十进制相加只有三种结果：0、1、2，所以代码里我们按照这三种分开讨论，根据step这个变量来考虑进位问题

到最后如果step结果为1，就说明字符串还需要多加1位

public String addBinary(String a, String b) {
    String res = "";
    char[] longArr = null;
    char[] shortArr = null;
    if (a.length() > b.length()) {
        longArr = a.toCharArray();
        shortArr = b.toCharArray();
    } else {
        longArr = b.toCharArray();
        shortArr = a.toCharArray();
    }
    int step = 0;
    for (int i = longArr.length - 1; i >= 0; i--) {
        int m = Integer.valueOf(String.valueOf(longArr[i]));
        int n = 0;
        if (i - (longArr.length - shortArr.length) >= 0) {
            n = Integer.valueOf(String.valueOf(shortArr[i - (longArr.length - shortArr.length)]));
        }

        int mn = m + n;
        if (mn == 0) {
            res = (mn + step) + res;
            step = 0;
        } else if (mn == 1) {
            if (step == 0) {
                res = mn + res;
            } else {
                res = "0" + res;
                step = 1;
            }
        } else if (mn == 2) {
            res = step + res;
            step = 1;
        }
    }
    if (step == 0) {
        return res;
    } else {
        return step + res;
    }
}
复制代码

官方题解的思路和我一致，但代码却完全不一样

直接通过char的位运算完成了进位的运算。

这里就要来说下char这个类型了。

java中使用unicode编码，所以char是16位，而ASCII码是8位，它包含在unicode编码中，范围是(0 ~ 127)

使用char可以进行字符运算

char a = 'g'
print(a + 1) //104

char c = '104' //报错，只能是1个字符

char c = 104 //表示'h'

char c = '0' //int值为48

char c = '1' //int值为49

所以 `1` - `0`，结果为1，可以用减`0`的方式转char为int，也可以用加`0`的方式转int为char
复制代码

StringBuilder res = new StringBuilder();
    int sum = 0;
    //倒序遍历
    for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
        // 因为是倒序遍历，所以只要i或j大于0就说明没有超过字符最大长度
        // - `0`是为了把char转成int
        sum += i >= 0 ? a.charAt(i) - '0' : 0;
        sum += j >= 0 ? b.charAt(j) - '0' : 0;
        //取模运算，可以算出当前位置计算过后的值
        res.append((char) (sum % 2 + '0'));
        //除法运算，可以算出进位是多少
        sum /= 2;
    }
    //说明最后还有进位，需要加到字符串上
    if (sum > 0) {
        res.append("1");
    }
    //倒序一下
    return res.reverse().toString();
复制代码

2. api

Java中有很多数值计算的api

先将 aa 和 bb 转化成十进制数，求和后再转化为二进制数。

• 如果字符串超过 3333 位，不能转化为 Integer
• 如果字符串超过 6565 位，不能转化为 Long
• 如果字符串超过 500000001500000001 位，不能转化为 BigInteger

对于较大的数字这种算法会报错

public String addBinary2(String a, String b) {
    return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
}
复制代码

示例超过int长度，报错了

所以改用BigInteger，但是需要手动导包

public String addBinary3(String a, String b) {
    return new BigInteger(a, 2).add(new BigInteger(b, 2)).toString(2);
}
复制代码