题目描述
题目链接: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
是否还留有进位更新至结果即可,代码如下:
#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