【LeetCode】求和

一、二进制求和

使用「竖式」计算十进制的加法的方式：

1.两个「加数」的右端对齐；
2.从最右侧开始，依次计算对应的两位数字的和。如果和大于等于 10，则把和的个位数字计入结果，并向前面进位。
3.依次向左计算对应位置两位数字的和，如果有进位需要加上进位。如果和大于等于 10，仍然把和的个位数字计入结果，并向前面进位。
4.当两个「加数」的每个位置都计算完成，如果最后仍有进位，需要把进位数字保留到计算结果中。

在代码中需要注意的有：
1.本题给出的二进制数字是字符串形式，不可以转化成 int 型，因为可能溢出；
2.两个「加数」的字符串长度可能不同；
3.在最后，如果进位 carry 不为 0，那么最后需要计算进位；
4.向结果字符串 res 拼接的顺序是向后拼接，返回时需要把 res 反转 。
代码中的巧妙之处：
while (i >= 0 || j >= 0 || carry != 0)含义：
字符串 a 和 b 只要有一个没遍历完，那么就继续遍历；
如果字符串 a 和 b 都遍历完了，但是最后留下的进位 carry != 0，那么需要把进位也保留到结果中。
取 digit 的时候，如果字符串 a 和 b 中有一个已经遍历完了（即 i < = 0 i <= 0i<=0 或者 j < = 0 j <= 0j<=0），则认为 a 和 b 的对应位置是 0 。

java代码

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder(); // 返回结果
        int i = a.length() - 1; // 标记遍历到 a 的位置
        int j = b.length() - 1; // 标记遍历到 b 的位置
        int carry = 0; // 进位
        while (i >= 0 || j >= 0 || carry != 0) { // a 没遍历完，或 b 没遍历完，或进位不为 0
            int digitA = i >= 0 ? a.charAt(i) - '0' : 0; // 当前 a 的取值
            int digitB = j >= 0 ? b.charAt(j) - '0' : 0; // 当前 b 的取值
            int sum = digitA + digitB + carry; // 当前位置相加的结果
            carry = sum >= 2 ? 1 : 0; // 是否有进位
            sum = sum >= 2 ? sum - 2 : sum; // 去除进位后留下的数字
            res.append(sum); // 把去除进位后留下的数字拼接到结果中
            i --;  // 遍历到 a 的位置向左移动
            j --;  // 遍历到 b 的位置向左移动
        }
        return res.reverse().toString(); // 把结果反转并返回
    }
}

深入理解StringBuffer和StringBuilder
StringBuffer、StringBuilder和String类似，底层也是用一个数组来存储字符串的值，并且数组的默认长度为16，即一个空的StringBuffer对象数组长度为16。实例化一个StringBuffer对象即创建了一个大小为16个字符的字符串缓冲区。但是​当我们调用有参构造函数创建一个StringBuffer对象时，数组长度就不再是16了，而是根据当前对象的值来决定数组的长度，数组的长度为“当前对象的值的长+16”。所以一个 StringBuffer 创建完成之后，有16个字符的空间可以对其值进行修改。如果修改的值范围超出了16个字符，会先检查StringBuffer对象的原char数组的容量能不能装下新的字符串，如果装不下则会对 char 数组进行扩容。

那StringBuffer是怎样进行扩容的呢？
扩容的逻辑就是创建一个新的 char 数组，将现有容量扩大一倍再加上2，如果还是不够大则直接等于需要的容量大小。扩容完成之后，将原数组的内容复制到新数组，最后将指针指向新的 char 数组。

StringBuffer append(xxx)：拼接字符串
StringBuffer delete(int start,int end)：删除指定范围的内容,左开右闭
StringBuffer replace(int start, int end, String str)：替换指定范围的内容
StringBuffer insert(int offset, xxx)：在指定位置插入指定的内容
StringBuffer reverse() ：把当前字符序列逆转

public int indexOf(String str) : 返回指定子字符串在当前字符串中第一次出现处的索引
public String substring(int start,int end) ：返回指定范围的子字符串
public int length() : 返回字符串的长度
public char charAt(int n ) : 获取指定索引处的字符
public void setCharAt(int n ,char ch) : 设置指定索引处的字符

面试题：String、StringBuffer和StringBuilder的异同？
相同点：底层都是通过char数组实现的
不同点：

1.String对象一旦创建，其值是不能修改的，如果要修改，会重新开辟内存空间来存储修改之后的对象；而StringBuffer和StringBuilder对象的值是可以被修改的；
2.StringBuffer几乎所有的方法都使用synchronized实现了同步，线程比较安全，在多线程系统中可以保证数据同步，但是效率比较低；而StringBuilder 没有实现同步，线程不安全，在多线程系统中不能使用 StringBuilder，但是效率比较高。
3.如果我们在实际开发过程中需要对字符串进行频繁的修改，不要使用String，否则会造成内存空间的浪费；当需要考虑线程安全的场景下使用 StringBuffer，如果不需要考虑线程安全，追求效率的场景下可以使用 StringBuilder。

二、加一 

class Solution {
    public int[] plusOne(int[] digits) {
        for(int i = digits.length - 1; i >= 0;i--){
            digits[i] = (digits[i] + 1) % 10;
            if(digits[i] != 0){
                return digits;
            }
        }
        //当循环遍历完之后，最高位还是等于0，说明最高位也进位了，应重新生成一个数组
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

 length()是求String字符串对象中字符的个数，而length是求字符串数组中有多少个字符串。