Fork me on GitHub

leetcode之67. 二进制求和

发表于 | 分类于
字数统计 485 字 | 阅读时长 2 分钟

题目描述：

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

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

示例 1:

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

示例 2:

1
2
3
> 输入: a = "1010", b = "1011"
> 输出: "10101"
>

解题思路：

思路一：

时间复杂度: $O(n)$, 空间复杂度: $O(n)$.

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
class Solution {
public:
	string addBinary(string a, string b) {
		string result = "";
		int i = a.length() - 1;
		int j = b.length() - 1;
		bool flag = false;
		int temp = 0;
		while(i >= 0 && j >= 0)
		{
    		// 判断是否进位
			if(flag)
   				 // 如果进位的话，还要加1
				temp = a[i] - '0' + b[j] - '0' + 1;
   			 // 否则不用加1
			else temp = a[i] - '0' + b[j] - '0';
   			 // 如果加完之后，大于2 ，说明进位了
			if(temp >= 2)
			{
   				 // 进位之后，
				temp = temp - 2;
   				 // flag为true
				flag = true;
			}
			else
			{
				flag = false;
			}
			result = to_string(temp) + result;
			i--,j--;
		}
		while(i >= 0)
		{
			if(flag) temp = a[i] - '0' + 1;
			else temp = a[i] - '0';
			if(temp >= 2)
			{
				temp = temp - 2;
				flag = true;
			}
			else flag = false;
			result = to_string(temp) + result;
			i--;
		}
		while(j >= 0)
		{
			if(flag) temp = b[j] - '0' + 1;
			else temp = b[j] - '0';
			if(temp >= 2)
			{
				temp = temp - 2;
				flag = true;
			}
			else flag = false;
			result = to_string(temp) + result;
			j--;
		}
		if(flag) result = "1" + result;
		return result;
	}
};

思路二：

时间复杂度: $O(n)$, 空间复杂度: $O(n)$.

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
class Solution {
public:
	string addBinary(string a, string b) {
		int i = a.size() - 1, j = b.size() - 1;
		string ret = "";
		int flag = 0;
		while(i >= 0 || j >= 0){
			// 对，这里的代码，很眼熟，与之前的中等难度的两数相加的解法很相似
			int at = (i >= 0) ? a[i] - '0' : 0;
			int bt = (j >= 0) ? b[j] - '0' : 0;
			int temp = at + bt + flag;
			// 这里的carry用来做标记，判断是否大于2
			// 这里除以2，如果大于2就会为1，不大于2就会为0
			flag = temp / 2;
			// 在这里，每次加到最前面
			ret = to_string(temp % 2) + ret;
			--i,--j;
		}
		// 这里，如果标记为1，那么头部加1
		if (flag != 0)
		{
			ret = "1" + ret;
		}
		return ret; 
	}
};