题目描述
给定两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
输入:a = “11”, b = “1”
输出：”100”
示例 2：
输入：a = “1010”, b = “1011”
输出：”10101”
提示：
1 <= a.length, b.length <= 104
a 和 b 仅由字符 ‘0’ 或 ‘1’ 组成
字符串如果不是 “0” ，就不含前导零
解析
思路1
先将两个数位数补齐，然后从最低位开始（即从右往左）依次求和，最后如果进位为 1，则将进位拼接到首位。思路简单，但是比较麻烦。
思路二
设 n = Math.max(a.length(), b.length())，i 为循环次数，此时可按如下规律取两个数对应数位的数：
- 较长字符串：
s.charAt(i)
- 较短字符串：
i - (n - s.length()) >= 0 ? s.charAt(i - (n - s.length())) : 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
| public String addBinary1(String a, String b) {
String str1 = a;
String str2 = b;
if (a.length() != b.length()) {
str1 = a.length() > b.length() ? a : b;
int length = Math.max(a.length(), b.length());
StringBuilder shortStr = new StringBuilder(a.length() < b.length() ? a : b);
while (shortStr.length() < length) {
shortStr.insert(0, "0");
}
str2 = shortStr.toString();
}
return getStringBuilder(str1, str2);
}
private static String getStringBuilder(String str1, String str2) {
char[] charArray1 = str1.toCharArray();
char[] charArray2 = str2.toCharArray();
int temp = 0;
int p = charArray1.length - 1;
StringBuilder result = new StringBuilder();
while (p >= 0) {
int curr = charArray1[p] - '0' + charArray2[p] - '0' + temp;
if (curr == 3) {
curr = 1;
temp = 1;
} else if (curr == 2) {
curr = 0;
temp = 1;
} else {
temp = 0;
}
result.insert(0, curr);
p--;
} if (temp == 1) {
result.insert(0, temp);
} return result.toString();
}
|
按规律找数和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public String addBinary(String a, String b) {
int n = Math.max(a.length(), b.length());
int temp = 0;
StringBuilder result = new StringBuilder();
for (int i = n - 1; i >= 0; i--) {
int num1 = a.length() == n ? a.charAt(i) - '0' : i - (n - a.length()) >= 0 ? a.charAt(i - (n - a.length())) - '0' : 0;
int num2 = b.length() == n ? b.charAt(i) - '0' : i - (n - b.length()) >= 0 ? b.charAt(i - (n - b.length())) - '0' : 0;
int curr = num1 + num2 + temp;
if (curr == 3) {
curr = 1;
temp = 1;
} else if (curr == 2) {
curr = 0;
temp = 1;
} else {
temp = 0;
}
result.insert(0, curr);
} if (temp == 1) {
result.insert(0, temp);
}
return result.toString();
}
|