LeetCode67-二进制求和
LeetCode67-二进制求和
给定两个二进制字符串,返回他们的和(用二进制表示)。
输入为非空字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
一、思路
这里只需要考虑溢出的情况就行了
处理溢出的方法:
设置一个新的数组用于存放相加的结果,低位存放低位计算的结果,高位计算的结果存放在高位
C++代码:
class Solution {
public:
string addBinary(string a, string b) {
string ans;
if (a.empty() && b.empty())
return ans;
int i = a.size() - 1, j = b.size() - 1;
int carry = 0, sum;
while (i >= 0 && j >= 0) {
sum = carry + (a[i--] - '0') + (b[j--] - '0');
if (sum == 0) {
ans.push_back('0');
carry = 0;
}
else if (sum == 1) {
ans.push_back('1');
carry = 0;
}
else if (sum == 2) {
ans.push_back('0');
carry = 1;
}
else if (sum == 3) {
ans.push_back('1');
carry = 1;
}
}
while (i >= 0) {
sum = carry + (a[i--] - '0');
if (sum == 0) {
ans.push_back('0');
carry = 0;
}
else if (sum == 1) {
ans.push_back('1');
carry = 0;
}
else if (sum == 2) {
ans.push_back('0');
carry = 1;
}
}
while (j >= 0) {
sum = carry + (b[j--] - '0');
if (sum == 0) {
ans.push_back('0');
carry = 0;
}
else if (sum == 1) {
ans.push_back('1');
carry = 0;
}
else if (sum == 2) {
ans.push_back('0');
carry = 1;
}
}
if (carry)
ans.push_back('1');
return reverseString(ans);
}
string reverseString(string s) {
string ans;
for (int i = s.size() - 1; i >= 0; i--) {
ans.push_back(s[i]);
}
return ans;
}
};
执行效率: