Description
Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
Example 1:
1
2
| Input: a = "11", b = "1"
Output: "100"
|
Example 2:
1
2
| Input: a = "1010", b = "1011"
Output: "10101"
|
分析
给定两个只包含 0 和 1 的非空字符串，求他们的二进制和。有题意得知，题目给定的字符串是合法的，可以省略输入合法性校验。
我们需要考虑的如下两个问题：
- a 和 b 的长度不一样
- 进位问题 (carry)
按如下步骤，
- 先选择字符串长度较小者为基准对字符串做反向遍历
- 每次遍历对对应字符和进位求和 ，再对和对 2 分别取余和取整，余数插入新字符串的头部，整数作为进位。
- 重复步骤 2 直到循环结束。
- 循环结束后如果进位非 0，则进位再与剩下的字符相加(如果有剩余字符)
- 返回结果
朴素解法
储备知识
String vs StringBuilder
在 Java 中，和常量一样 String 是不可变的(immutable) ，因此，对字符串做可变(insert/update/delete等)操作时，会产生新的字符串，旧的字符串会当作垃圾丢弃。频繁的字符串操作严重降低了性能，对垃圾回收造成较大压力，所以 Java 提供 StringBuilder 类型用于字符串的可变操作， StringBuilder 提供了 append、delete、insert 等接口。
StringBuilder vs StringBuffer
StringBuffer 和 StringBuilder 类似，也是用于字符串的可变操作。然而任何操作在多线程中都会存在状态同步(原子操作/一致性)问题，StringBuffer 是线程安全的，因此开销会大一些，在单线程中使用 StringBuffer 对字符串做操作是较好的选择。
StringBuilder 提供的接口
StringBuilder 含有 String 的大部分方法(是否是继承同一个父类？或实现同一个接口？没做过调查)
| 想要的操作 |
提供的接口 |
注解 |
| 追加一个字符串 |
append(String s) |
也可以追加 char/int/boolean等类型，功能和 + 类似 |
| 删除指定位置的字符 |
deleteCharAt(int index) |
|
| 指定位置插入字符 |
insert(int offset, char x) |
也可以插入String/int/boolean 等 |
代码
按照如上分析，我们可以使用 StringBuilder 对字符串做操作，使用其提供的 insert 方法实现头部插入，具体如下(代码未实现完)
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
| class Solution {
public String addBinary(String a, String b) {
int aLen = a.length();
int bLen = b.length();
int i, j;
if (aLen < bLen) {
i = aLen - 1;
j = bLen - aLen - 1;
} else {
i = bLen - 1;
j = aLen - bLen - 1;
}
StringBuilder result = new StringBuilder();
int carry = 0;
while (i >= 0)
int sum = (a.charAt(i) - '0') + (b.charAt(i) - '0') + carry;
carry = (sum >> 1);
result.insert(0, sum % 2);
i--;
}
while (j >= 0) {
carry = (sum >> 1);
result.insert(0, sum % 2);
j--;
}
if (carry > 0) {
result.insert(0, carry);
}
result.toString();
}
}
|
写了 80% 的时候发现，特殊逻辑太多，进来先判断 a 和 b 的长度，后续还要做一次判断，该方法太繁琐，我决定再作思考，优化特殊逻辑。
刚去了一趟厕所，想了一下可以在循环体中做特殊逻辑，如下，
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
| class Solution {
public String addBinary(String a, String b) {
int i = a.length() - 1;
int j = b.length() - 1;
StringBuilder result = new StringBuilder();
int carry = 0;
while (i >= 0 || j >= 0) {
int num1 = 0;
int num2 = 0;
if (i >= 0) {
num1 = (a.charAt(i) - '0');
}
if (j >= 0) {
num2 = (b.charAt(j) - '0');
}
int sum = num1 + num2 + carry;
carry = (sum >> 1);
result.insert(0, sum % 2);
i--;
j--;
}
if (carry > 0) {
result.insert(0, carry);
}
return result.toString();
}
}
|
提交后 Ac 了，内存使用打败 99.94%，时间就刚刚及格，62.66%。分析了以下，慢的原因是多次头部插入 result.insert，像这个问题，每次遍历的时候会往头部插入，最后输出有从头开始，很典型的先进后出问题，用栈优化以下就好啦。
使用 Stack
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
| class Solution {
public String addBinary(String a, String b) {
int i = a.length() - 1;
int j = b.length() - 1;
Stack<Integer> bucket = new Stack<>();
StringBuilder result = new StringBuilder();
int carry = 0;
while (i >= 0 || j >= 0) {
int num1 = 0;
int num2 = 0;
if (i >= 0) {
num1 = (a.charAt(i) - '0');
}
if (j >= 0) {
num2 = (b.charAt(j) - '0');
}
int sum = num1 + num2 + carry;
carry = (sum >> 1);
bucket.push(sum % 2);
i--;
j--;
}
if (carry > 0) {
bucket.push(carry);
}
while (!bucket.isEmpty()) {
result.append(bucket.pop());
}
return result.toString();
}
}
|
本来打算使用 Stack 优化朴素算法中的频繁 Insert 问题，结果花费了 3ms，之战胜了 13% 的提交，最终参考了别人的提交，优化思路是每次都在结果中 append，最后在 reverse 字符串。
先 Append 后 Reverse
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
| class Solution {
public String addBinary(String a, String b) {
int i = a.length() - 1;
int j = b.length() - 1;
StringBuilder result = new StringBuilder();
int carry = 0;
while (i >= 0 || j >= 0) {
int num1 = 0;
int num2 = 0;
if (i >= 0) {
num1 = (a.charAt(i) - '0');
}
if (j >= 0) {
num2 = (b.charAt(j) - '0');
}
int sum = num1 + num2 + carry;
carry = (sum >> 1);
result.append(sum % 2);
i--;
j--;
}
if (carry > 0) {
result.append(carry);
}
return result.reverse().toString();
}
}
|
果然，提交后内存和时间基本都是最优状态。
