Leetcode-67 —— Add Binary

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)

按如下步骤,

  1. 先选择字符串长度较小者为基准对字符串做反向遍历
  2. 每次遍历对对应字符和进位求和 ,再对和对 2 分别取余和取整,余数插入新字符串的头部,整数作为进位。
  3. 重复步骤 2 直到循环结束。
  4. 循环结束后如果进位非 0,则进位再与剩下的字符相加(如果有剩余字符)
  5. 返回结果

朴素解法

储备知识

  • 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) {
// int sum = (a.charAt(i) - '0') + (b.charAt(i) - '0') + carry;
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();
}
}

果然,提交后内存和时间基本都是最优状态。

本文标题:Leetcode-67 —— Add Binary

文章作者:Syncher

发布时间:2019年07月10日 - 11:07

最后更新:2019年07月10日 - 04:07

原始链接:https://0x400.com/2019-07-10-lc-67-add-binary.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。