C++刷leetcode（67. 二进制求和）【递归】
题目描述：给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
提示：
每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-binary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
void dfs(string & a, string & b, string& res, int cura, int curb, int store){
if(cura < 0 && curb < 0){
if(store != 0) res += '1';
return;
}
if(cura < 0){
int temp = b - '0' + store;
if(temp >= 2){
store = 1;
if(temp == 2)res += '0';
else res += '1';
}
else if(temp < 2){
char temp2 = temp + '0';
res += temp2;
store = 0;
}
dfs(a, b, res, -1, curb - 1, store);
}
else if(curb < 0){
int temp = a - '0' + store;
if(temp >= 2){
store = 1;
if(temp == 2)res += '0';
else res += '1';
}
else if(temp < 2){
char temp2 = temp + '0';
res += temp2;
store = 0;
}
dfs(a, b, res, cura-1, -1, store);
}
else{
int temp = a - '0' + b - '0' + store;
if (temp >= 2){
store = 1;
if(temp == 2)res += '0';
else res += '1';
}else if(temp < 2){
char temp2 = temp + '0';
res += temp2;
store = 0;
}
dfs(a, b, res, cura-1, curb-1, store);
}
}
string addBinary(string a, string b) {
string res;
dfs(a, b, res, a.size()-1, b.size() - 1, 0);
reverse(res.begin(), res.end());
return res;
}
};
页:
[1]