⭐每天一道leetcode：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" ，就不含前导零

⭐题目思路

还是先提取一下题目特征点：

• 二进制

• 字符串

• 相加

我的思路是模拟二进制数相加的过程，也就是从最后边的数字开始，逢二进一。那么我们就需要一个变量carry来记录同一位上两个数的累加和，并将进位这件事一直向前传递。

⭐代码

class Solution 
{
public:
    string addBinary(string a, string b) 
    {
        string ans;
        //将两个字符串反转
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
​
        int n=max(a.size(),b.size()),carry=0;//carry用来记录进位与否
        for(int i=0;i<n;i++) 
        {
            //如果i未超出a的长度，那么记录该位是否为1
            if(i<a.size()&&a[i]=='1') carry++;
            //b同理
            if(i<b.size()&&b[i]=='1') carry++;
            ans+=(carry%2)?'1':'0';//对2取余，为0就是需要进位
            carry/=2;//这样，如果需要进位，会剩1，不进位剩0
        }
​
        if(carry)//最后仍需进位 
        {
            ans+='1';
        }
        reverse(ans.begin(),ans.end());//反转字符串
​
        return ans;
    }
};
​

但是这个代码的用时太长了，通过和官方题解对比，我发现了几个比较重要的提分点：

• 三目运算符比普通if语句耗时少

• 字符串的push_back比+=耗时少

• size_t类型比int类型耗时少

据此优化如下

class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
​
        int n = max(a.size(), b.size()), carry = 0;
        for (size_t i = 0; i < n; ++i) {
            carry += i < a.size() ? (a.at(i) == '1') : 0;
            carry += i < b.size() ? (b.at(i) == '1') : 0;
            ans.push_back((carry % 2) ? '1' : '0');
            carry /= 2;
        }
​
        if (carry) {
            ans.push_back('1');
        }
        reverse(ans.begin(), ans.end());
​
        return ans;
    }
};

提交结果

🌮欢迎大家提供更高效的代码，如果过后有更优化的思路我还会继续更新的，大家评论区见！

点赞收藏不迷路⭐~