LeetCode：Add Binary（二进制求和）

77 阅读 0 评论 51 点赞

我是靠谱客的博主独特口红，最近开发中收集的这篇文章主要介绍LeetCode：Add Binary（二进制求和），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example1:

Input: a = "11", b = "1"
Output: "100"

Example2:

Input: a = "1010", b = "1011"
Output: "10101"

思路

按照笔算的思路，从最低位开始对a和b的数进行加法运算，难点在于进位的控制和最高位非零问题。

从最低位开始按位求和并加上进位值，结果除以2并求余数，得到进位值和当前位上的值，使用insert将当前位上的值插入字符串，直到达到较短字符串的长度，然后单独对较长字符串的剩余部分和进位值求和。

最后对得到的字符串从最左边定位第一个非零字符，返回非零字符之后的字符串。

代码

class Solution {
public:
    string addBinary(string a, string b) {
        int sizea = a.size();
        int sizeb = b.size();

        string res;
        if(sizea<sizeb)
        {
            string temp;
            temp=a;
            a=b;
            b=temp;
            int n=sizea;
            sizea=sizeb;
            sizeb=n;
        }
        int temp=0;
        int h=0;
        for(int i=0;i<sizeb;i++)
        {
            temp+=a[sizea-1-i]-'0'+b[sizeb-1-i]-'0';
            h = temp%2;
            temp = temp/2;
            res.insert(0,1,'0'+h);
        }
        for(int i=0;i<sizea-sizeb;i++)
        {
            temp+=a[sizea-sizeb-1-i]-'0';
            h = temp%2;
            temp = temp/2;
            res.insert(0,1,'0'+h);
        }
        res.insert(0,1,'0'+temp);
        int sizer = res.size();
        for(int i=0;i<sizer;i++)
        {
            if(res[i]!='0')
            {
                res=res.substr(i,sizer-i);
                return res;
            }
        }
        return "0";
    }
};