算法练习——二进制求和

2021年1月31日每日算法练习67. 二进制求和,这道题类似于昨天做的加一,只不过从十进制换算成了二进制。先将两个长度比较,获取最大值,并且求出两个数组的长度差,以最长的字符串作为主数组,短的为辅数组,用一个变量记录余数。将主数组从尾向头遍历,当下标与长度差大于等于0并且小于辅数组的长度时,进行求和,这样就像是将两个数组的尾部对齐,相应位上的数字相加,加上对应的进位数,最后余2求得十分进位,加入到列表中。代码如下:

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
class Solution {
public String addBinary(String a, String b) {
int aLen = a.length(), bLen = b.length();
char[] mainArray = aLen > bLen ? a.toCharArray() : b.toCharArray();
char[] subArray = aLen <= bLen ? a.toCharArray() : b.toCharArray();
int max = Math.max(aLen, bLen);
int offset = Math.abs(aLen - bLen);
int rest = 0;
LinkedList<Integer> result = new LinkedList<>();
for (int i = max - 1; i >= 0; i--) {
int sum = mainArray[i] - '0';
if (0 <= i - offset && i - offset < subArray.length) {
sum += subArray[i - offset] - '0';
}
sum += rest;
rest = sum / 2;
sum %= 2;
result.addFirst(sum);
}
if (rest != 0) {
result.addFirst(rest);
}
StringBuilder builder = new StringBuilder();
for (Integer i : result) {
builder.append(i);
}
return builder.toString();
}
}

然后发现好像不需要链表也可以,直接构建字符串即可,因此:

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
class Solution {
public String addBinary(String a, String b) {
int aLen = a.length(), bLen = b.length();
char[] mainArray = aLen > bLen ? a.toCharArray() : b.toCharArray();
char[] subArray = aLen <= bLen ? a.toCharArray() : b.toCharArray();
int max = Math.max(aLen, bLen);
int offset = Math.abs(aLen - bLen);
int rest = 0;
StringBuilder builder = new StringBuilder();
for (int i = max - 1; i >= 0; i--) {
int sum = mainArray[i] - '0';
if (0 <= i - offset && i - offset < subArray.length) {
sum += subArray[i - offset] - '0';
}
sum += rest;
rest = sum / 2;
sum %= 2;
builder.insert(0, sum);
}
if (rest != 0) {
builder.insert(0, rest);
}
return builder.toString();
}
}

最后附上官方题解的三种解答,代码还可以再简化一些,使得空间复杂度下降。