问题

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"

分析

这道题本来不想放上来的，不涉及多少算法上的问题，但是记录一些必要的字符串方法是很有必要的

StringBuffer、StringBuilder与String

这三兄弟看似一样，实则区别很小，但是终归还是有区别的

  1. 运行速度方面：StringBuilder > StringBuffer > String
    前两个我们抛开不谈，说说为什么 String 最慢，因为 String 为字符串常量，而 StringBuilder 和 StringBuffer 均为字符串变量，即 String 对象一旦创建之后该对象是不可更改的，但后两者的对象是变量，是可以更改的。

    1
    2
    3
    4
    String str="abc";
    System.out.println(str);
    str=str+"de";
    System.out.println(str);

    如果运行这段代码会发现先输出 “abc”，然后又输出 “abcde” ，好像是 str 这个对象被更改了，其实，这只是一种假象罢了，JVM 对于这几行代码是这样处理的，首先创建一个 String 对象 str ，并把 “abc” 赋值给 str ，然后在第三行中，其实 JVM 又创建了一个新的对象也名为 str ，然后再把原来的 str 的值和 “de” 加起来再赋值给新的 str ，而原来的 str 就会被 JVM 的垃圾回收机制（GC）给回收掉了，所以， str 实际上并没有被更改，也就是前面说的 String 对象一旦创建之后就不可更改了。所以， Java 中对 String 对象进行的操作实际上是一个不断创建新的对象并且将旧的对象回收的一个过程，所以执行速度很慢。

  2. 线程安全方面
    StringBuffer 线程安全，而 StringBuilder 非线程安全，主要由于 Builder 中不带锁方法。这里我们不详细讨论。

  3. 方法
    String的方法

    1
    2
    3
    4
    5
    6
    7
    String a = "Hello World"
    a.charAt(1);//寻找第1个元素
    byte b[] = a.getBytes();//转换成比特数组
    char[]b = a.toCharArray();//转换成字符数组
    b.concat(a);//连接两个字符串
    a.indexOf("o"));//“o”第一次出现的位置
    a.lastIndexOf("o");//“o”最后一次出现的位置

    StringBuffer的方法

    1
    2
    3
    4
    5
    sb1.append(" World");//在尾部添加字符串
    sb1.insert(1, "ME");//在指定位置后面添加字符串
    sb1.deleteCharAt(0)；//删除指定位置元素
    sb1.reverse();//反转字符串
    sb1.toString();//转换成String类型

  4. 将字符串中的字符型数字转换成int

    1
    int number = b.charAt(i) - '0';

String 为什么要设计成不可变的？(2019-5-14 更新)

  1. 字符串常量池的需要
    字符串常量池(String pool, String intern pool, String保留池) 是Java堆内存中一个特殊的存储区域, 当创建一个String对象时,假如此字符串值已经存在于常量池中,则不会创建一个新的对象,而是引用已经存在的对象。还可以使用 String 的 intern() 方法在运行过程中将字符串添加到 String Pool 中。

    如下面的代码所示,将会在堆内存中只创建一个实际String对象.

    1
    2
    String s1 = "abcd";
    String s2 = "abcd";

    示意图如下所示:
    string 常量池
    假若字符串对象允许改变,那么将会导致各种逻辑错误,比如改变一个对象会影响到另一个独立对象. 严格来说，这种常量池的思想,是一种优化手段.

    String 不可变性天生具备线程安全，可以在多个线程中安全地使用。

  2. 允许String对象缓存HashCode
    Java中String对象的哈希码被频繁地使用, 比如在hashMap 等容器中。
    字符串不变性保证了hash码的唯一性,因此可以放心地进行缓存.这也是一种性能优化手段,意味着不必每次都去计算新的哈希码. 在String类的定义中有如下代码:

    1
    private int hash;//用来缓存HashCode

回到这道题

这道题说两个二进制数相加，得到一个二进制数，首先顺序肯定是从后向前，按位计算，其次要选择一个变量来判断是否应该进位（carry）。我们将每位算出的结果取余保存在一个StringBuffer中，然后将得到的数除以2来判断下一个是否进位。最后返回StringBuffer的反转。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() -1, carry = 0;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (j >= 0) sum += b.charAt(j--) - '0';
            if (i >= 0) sum += a.charAt(i--) - '0';
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry != 0) sb.append(carry);
        return sb.reverse().toString();
    }
}

源代码