C++刷leetcode（67. 二进制求和）【递归】

糖逗

题目描述：

1. 给你两个二进制字符串，返回它们的和（用二进制表示）。
   
2. 
   
3. 输入为 非空 字符串且只包含数字 1 和 0。
   
4. 
   
5.  
   
6. 
   
7. 示例 1:
   
8. 
   
9. 输入: a = "11", b = "1"
   
10. 输出: "100"
    
11. 示例 2:
    
12. 
    
13. 输入: a = "1010", b = "1011"
    
14. 输出: "10101"
    
15.  
    
16. 
    
17. 提示：
    
18. 
    
19. 每个字符串仅由字符 '0' 或 '1' 组成。
    
20. 1 <= a.length, b.length <= 10^4
    
21. 字符串如果不是 "0" ，就都不含前导零。
    
22. 
    
23. 来源：力扣（LeetCode）
    
24. 链接：https://leetcode-cn.com/problems/add-binary
    
25. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     void dfs(string & a, string & b, string& res, int cura, int curb, int store){
   
4.         if(cura < 0 && curb < 0){
   
5.             if(store != 0) res += '1';
   
6.             return;
   
7.         }
   
8.         if(cura < 0){
   
9.             int temp = b[curb] - '0' + store;
   
10.             if(temp >= 2){
    
11.                 store = 1;
    
12.                 if(temp == 2)res += '0';
    
13.                 else res += '1';
    
14.             }
    
15.             else if(temp < 2){
    
16.                 char temp2 = temp + '0';
    
17.                 res += temp2;
    
18.                 store = 0;
    
19.             }
    
20.             dfs(a, b, res, -1, curb - 1, store);
    
21.         }
    
22.         else if(curb < 0){
    
23.             int temp = a[cura] - '0' + store;
    
24.             if(temp >= 2){
    
25.                 store = 1;
    
26.                 if(temp == 2)res += '0';
    
27.                 else res += '1';
    
28.             }
    
29.             else if(temp < 2){
    
30.                 char temp2 = temp + '0';
    
31.                 res += temp2;
    
32.                 store = 0;
    
33.             }
    
34. 
    
35.             dfs(a, b, res, cura-1, -1, store);
    
36.         }
    
37.         else{
    
38.             int temp = a[cura] - '0' + b[curb] - '0' + store;
    
39.             if (temp >= 2){
    
40.                 store = 1;
    
41.                 if(temp == 2)res += '0';
    
42.                 else res += '1';
    
43.             }else if(temp < 2){
    
44.                 char temp2 = temp + '0';
    
45.                 res += temp2;
    
46.                 store = 0;
    
47.             }
    
48.             dfs(a, b, res, cura-1, curb-1, store);
    
49.         }
    
50.     }
    
51.     string addBinary(string a, string b) {
    
52.         string res;
    
53.         dfs(a, b, res, a.size()-1, b.size() - 1, 0);
    
54.         reverse(res.begin(), res.end());
    
55.         return res;
    
56.     }
    
57. };

复制代码