LeetCode刷题（31）～二进制求和【字符串易错！】

题目描述

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"
输出: "100"

  

 

  
1
  
2
 

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

  

 

  
1
  
2
 

提示：

• 每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
• 1 <= a.length, b.length <= 10^4
• 字符串如果不是 “0”，就都不含前导零。

解答

代码

class Solution {
public: string addBinary(string a, string b) { int i = a.length() - 1; int j = b.length() - 1; int carry = 0; string builder; //循环相加两个字符串相同长度的低位数部分 while (i >= 0 && j >= 0) { int sum = carry; sum += a.at(i--) - '0';//将char类型的1转化为int类型的1 sum += b.at(j--) - '0'; carry = sum / 2; //是否进位 builder+=to_string((sum % 2)); } // 如果 a 还没遍历完成（a串比b串长），则继续遍历添加 a 的剩余部分 while (i >= 0) { int sum = carry + a.at(i--) - '0'; carry = sum / 2; builder+=to_string(sum % 2); } // 如果 b 还没遍历完成（b串比a串长），则继续遍历添加 b 的剩余部分 while (j >= 0) { int sum = carry + b.at(j--) - '0'; carry = sum / 2; builder+=to_string(sum % 2); } //如果 carry 不等于0 还有个进位数没加进去，需要补充 if (carry == 1) { builder+=to_string(carry); } //反转字符串获得正常结果 reverse(builder.begin(),builder.end()); return builder; }
};

  

 

  
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
 

运行结果

代码（巧妙！！！）

string addBinary(string a, string b) { string result=""; // 反转 a、b reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); // 求出a b 较长字符串的长度 int n=max(a.size(),b.size()); // 进位 初始为0 int count=0; for(int i=0;i<n;++i) { // 这一步非常巧妙 // i<a.size()? (a[i]=='1'):0 // 若i<a.size(),  返回  a[i]=='1' ，若符合相等，则直接返回数字1 反之 返回数字0 // 若i>=a.size() 就返回0 其实就是填充0 只是并不是真正的填充，只是计算的时候加上0 // 非常好的一个写法 count+= i<a.size()? (a[i]=='1'):0; count+= i<b.size()? (b[i]=='1'):0; // 计算结果 并 更新进位 result+=(count%2)? '1':'0'; count/=2; } // 如最后进位为1 就需要在字符串最后加上‘1’ 即可 if(count==1) result+='1'; // 记得再反转回去 reverse(result.begin(),result.end()); return result; }

  

 

  
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
 

运行结果

C++测试代码

#include <iostream>
#include<vector>
#include<unordered_map>
#include<stack>
#include <algorithm>
using namespace std;
// 方法一
string addBinary_1(string a, string b) { int i = a.length() - 1; int j = b.length() - 1; int carry = 0; string builder; //循环相加两个字符串相同长度的低位数部分 while (i >= 0 && j >= 0) { int sum = carry; sum += a.at(i--) - '0';//将char类型的1转化为int类型的1 sum += b.at(j--) - '0'; carry = sum / 2; //是否进位 builder+=to_string((sum % 2)); } // 如果 a 还没遍历完成（a串比b串长），则继续遍历添加 a 的剩余部分 while (i >= 0) { int sum = carry + a.at(i--) - '0'; carry = sum / 2; builder+=to_string(sum % 2); } // 如果 b 还没遍历完成（b串比a串长），则继续遍历添加 b 的剩余部分 while (j >= 0) { int sum = carry + b.at(j--) - '0'; carry = sum / 2; builder+=to_string(sum % 2); } //如果 carry 不等于0 还有个进位数没加进去，需要补充 if (carry == 1) { builder+=to_string(carry); } //反转字符串获得正常结果 reverse(builder.begin(),builder.end()); return builder; }
// 方法二 将短的字符串填充0 再依次相加 巧妙
string addBinary_2(string a, string b) { string result=""; // 反转 a、b reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); // 求出a b 较长字符串的长度 int n=max(a.size(),b.size()); // 进位 初始为0 int count=0; for(int i=0;i<n;++i) { // 这一步非常巧妙 // i<a.size()? (a[i]=='1'):0 // 若i<a.size(),  返回  a[i]=='1' ，若符合相等，则直接返回数字1 反之 返回数字0 // 若i>=a.size() 就返回0 其实就是填充0 只是并不是真正的填充，只是计算的时候加上0 // 非常好的一个写法 count+= i<a.size()? (a[i]=='1'):0; count+= i<b.size()? (b[i]=='1'):0; // 计算结果 并 更新进位 result+=(count%2)? '1':'0'; count/=2; } // 如最后进位为1 就需要在字符串最后加上‘1’ 即可 if(count==1) result+='1'; // 记得再反转回去 reverse(result.begin(),result.end()); return result; }
int main()
{ string a="100"; string b="010"; cout<<addBinary_2(a,b)<<endl; return 0;
}


  

 

  
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
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
 

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-binary
参考：https://leetcode-cn.com/problems/add-binary/solution/er-jin-zhi-qiu-he-by-leetcode-solution/

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/107899472