LeetCode 67. 二进制求和 | C++语言版_两个字符串二进制求和c语言

LeetCode 67. 二进制求和

题目描述

题目地址：67. 二进制求和
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

解题思路

思路一：使用栈

代码实现

C++

class Solution {
public:
    string addBinary(string a, string b) {
        //输入：a = "1010", b = "1011"
        //输出："10101"
        int al=a.size();
        int bl=b.size();

        //让两个字符串等长，若不等长，在短的字符串前补零，否则之后的操作会超出索引
        while(al>bl){
            b='0'+b;
            ++bl;
        }
        while(al<bl){
            a='0'+a;
            ++al;
        }

        //进位
        int carry=0;
        //从后到前遍历所有的位数，同位相加
        for(int i=al-1;i>=0;i--){
            int sum=a[i]-'0'+b[i]-'0'+carry;
            //本位数值
            a[i]=(sum)%2+'0';
            //更新进位
            carry=sum/2;
        }

        //有溢出(第0位数的相加是单独处理的，是否需要在最前面加一位数‘1’)
        if(carry>0) a='1'+a;
        return a;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

在这里插入代码片
1

运行结果

参考文章：

https://leetcode.cn/problems/add-binary/solutions/7497/c-xiang-xi-ti-jie-bu-zou-qing-xi-by-youlookdelicio/

思路二：减少遍历节点数

代码实现

在这里插入代码片
1

运行结果

参考文章：