题目

点击查看原题

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

示例 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字符串中的结果
    }
};
End

本文标题:LeetCode 第67题 二进制求和

本文链接:http://chisato.cn/index.php/archives/190/

除非另有说明,本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

声明:转载请注明文章来源。

最后修改:2022 年 07 月 23 日 10 : 46 PM
如果觉得我的文章对你有用,请随意赞赏