XTAO's Tech Blog
0%

[Leetcode]67. Add Binary(C++)

发表于 分类于 ， 评论数：
1.3k 1 分钟

题目描述

题目链接：67. 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.

例子

例子 1

Input: a = “11”, b = “1”
Output: “100”

例子 2

Input: a = “1010”, b = “1011”
Output: “10101”
Explanation:

Constraints

  • Each string consists only of '0' or '1' characters.
  • 1 <= a.length, b.length <= 10^4
  • Each string is either "0" or doesn’t contain any leading zero.

解题思路

解题思路比较简单，分别用指针变量指向两个字符串的末端，从后往前遍历。并且用一个布尔值表示当前是否有进位。遍历每一位时用一个整型变量
sum 记录和(a[ptr1] + b[ptr2] + flag)，当 sum >= 2 时表示当前有进位，记录在 flag 中并将 sum 减2。遍历结束后检查 flag
是否还留有进位更新至结果即可，代码如下：

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
35
36
37
38
39
#include <string>
#include <algorithm>

class Solution {
public:
    std::string addBinary(std::string a, std::string b) {
        bool flag = false;
        int ptr1 = a.length() - 1, ptr2 = b.length() - 1;
        std::string result = "";
        while (ptr1 >= 0 || ptr2 >= 0) {
            int sum = 0;
            if (ptr1 >= 0 && a[ptr1] == '1') {
                sum++;
            }
            if (ptr2 >= 0 && b[ptr2] == '1') {
                sum++;
            }
            if (flag) {
                sum++;
                flag = false;
            }
            if (sum >= 2) {
                flag = true;
                sum -= 2;
            }

            ptr1--;
            ptr2--;
            result += '0' + sum;
        }

        if (flag) {
            result += '1';
        }

        std::reverse(result.begin(), result.end());
        return result;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

GitHub 代码同步地址： 67.AddBinary.cpp

其他题目：
GitHub: Leetcode-C++-Solution
博客： Leetcode-Solutions

推荐文章