LeetCode 第67题 二进制求和

题目

点击查看原题

给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

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

示例 2:

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

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

思路分析

二进制求和，满二进一
首先让两个字符串等长，若不等长，在短的字符串前补零，否则之后的操作会超出索引。
然后从后到前遍历所有的位数，同位相加，这里有一个点，用的是字符相加，利用 ASCII 码，字符在内部都用数字表示，我们不需要知道具体数值，但可知 ‘0’-‘0’ = 0 ，‘0’+1=‘1’，以此类推 。字符的加减，大小比较，实际上都是内部数字的加减，大小比较
判断相加后的字符，若大于等于字符 ‘2’，下一位需要进一
第 0 位数的相加在这里是单独处理的，因为它可能涉及到字符的插入（即是否需要在最前面加一位数 ‘1’

代码解答

class Solution {
public:
    string addBinary(string a, string b) {
        int alen=a.size();//获取a字符串长度
        int blen=b.size();//获取b字符串长度
        while(alen>blen)//当a长度小于b时，在b字符串前面补0占位,同时字符串长度加1
        {
            b='0' + b;
            ++blen;
        }
        while(blen>alen)//当b长度小于a时，在a字符串前面补0占位,同时字符串长度加1
        {
            a='0' + a;
            ++alen;
        }
        int carry=0;//声明一个代表进位的变量
        for(int i=a.size()-1;i>=0;i--)//倒序循环，从后向前两个字符串每一位相加
        {
            int sum = a[i] - '0' + b[i] - '0' + carry;//通过ASCII码相加，所以分别减去‘0’，而且要加上进位的carry的值。
            a[i] = (sum)%2 + '0';//判断相加后的值是否大于2，如果结果为0则赋值0，若结果为1赋值1，若结果为2也赋值0；最后加上‘0’的ASCII的数值
            carry = sum / 2;//若相加结果为2，则需要进位，carry=2/2=1
        }
        if(carry>0)//最后判断两个字符串的第0位相加是否需要进位，若需要则进入这个if
        {
            a='1'+a;//在a字符串前面加一个‘1’占位
        }

        return a;//返回a字符串中的结果
    }
};