「力扣」67. 二进制求和

题目描述

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

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

示例 2：

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

提示：

• 1 <= a.length, b.length <= 104
• a 和 b 仅由字符 '0' 或 '1' 组成
• 字符串如果不是 "0" ，就不含前导零

题解

进制转换

看到这个题我的第一想法是将两个字符串转化为十进制，然后求和，再将十进制转化为二进制，得到如下代码：

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

提交到力扣：

提示我有很多用例未通过，比如：

a =
"10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101"
b =
"110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"

忽然明白，原来位数过大了，因为int最大是32位，上面的字符数量明显大于32。

数学计算

上面将整个字符串通过进制转换是不行的，可以考虑循环字符串，两个字符串右对齐，相同索引位置计算得到结果，然后除以2，判断是否需要进位。

那么如何迭代呢？因为两个串可能是长度不同的，最终的结果长度肯定是等于原串中长度大的长度或者加一，所以采用长度大的作为迭代的索引的最大值，可以定义两个指针i和j，其中i初始的时候指向长串(max)的最大值，j指向短串(min)的最大值，每次迭代i--,j--。

在迭代外层我们定义一个变量c，该变量的含义是max[i] + min[j] + c的值（计算当前i和j的值和进位的总值），每次循环后要重新通过c /= 2来判断是否当前计算是否要进位。

当i --, j--的时候可能出现j < 0的情况，比如下图：

这个时候要做判断，如果j < 0的时候，可以认为当前值是'0'。

如果循环结束后，c == 1说明进位，则只需要将字符串前加上一个1即可，完整代码如下：

class Solution {
    public String addBinary(String a, String b) {
        String max = a.length() >= b.length() ? a : b; // 计算出来长串max
        String min = a.length() < b.length() ? a : b; // 计算出来段串min
        StringBuilder sb = new StringBuilder(); // 用于保存结果
        int c = 0; // 保存进位值
        int j = min.length() - 1; // 短串的初始化索引
        for (int i = max.length() - 1; i >= 0; i--) {
            char ch1 = max.charAt(i); // 长串的值
            char ch2 = j < 0 ? '0' : min.charAt(j); // 短串的值，如果索引小于0，则设置为`0`.
            c += (ch1 - '0') + (ch2 - '0'); // 当前位置的总值， char类型运算会转化为int。
            sb.insert(0, (c % 2)); //每次将值插入到字符串首位置
            c /= 2; // 是否进位
            j--; // 索引递减
        }
        if (c == 1) { // 迭代完毕后依然需要进位，则前面补1
             sb.insert(0, 1);
        }
        return sb.toString();
    }
}

提交到力扣：

额。。内存只击败了34.79%的Java用户，性能低在哪里？

看了下力扣的题解，跟我思路差不多，不同之处是它没有使用sb.insert，而是先使用append，最后反转字符串了，尝试修改下代码：

class Solution {
    public String addBinary(String a, String b) {
        String max = a.length() >= b.length() ? a : b; // 计算出来长串max
        String min = a.length() < b.length() ? a : b; // 计算出来段串min
        StringBuilder sb = new StringBuilder(); // 用于保存结果
        int c = 0; // 保存进位值
        int j = min.length() - 1; // 短串的初始化索引
        for (int i = max.length() - 1; i >= 0; i--) {
            char ch1 = max.charAt(i); // 长串的值
            char ch2 = j < 0 ? '0' : min.charAt(j); // 短串的值，如果索引小于0，则设置为`0`.
            c += (ch1 - '0') + (ch2 - '0'); // 当前位置的总值， char类型运算会转化为int。
            sb.append(c % 2); //每次将值插入到字符串首位置
            c /= 2; // 是否进位
            j--; // 索引递减
        }
        if (c == 1) { // 迭代完毕后依然需要进位，则前面补1
            sb.append('1');
        }
        return sb.reverse().toString();
    }
}

再次提交到力扣：

似乎差不多。