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)

按如下步骤，

先选择字符串长度较小者为基准对字符串做反向遍历
每次遍历对对应字符和进位求和，再对和对 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 方法实现头部插入，具体如下(代码未实现完)

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 的长度，后续还要做一次判断，该方法太繁琐，我决定再作思考，优化特殊逻辑。

刚去了一趟厕所，想了一下可以在循环体中做特殊逻辑，如下，

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

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

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();
    }
}

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