4.4 leet66|67 plus

66. Plus One
    https://leetcode.com/problems/plus-one/

一开始没有考虑到溢出的问题，我是这样写的。

1. 如果最后一位不是9，直接加一
2. 是9 就将数组转为整数number，将整数加一，在将整数转为字符串s
3. 将字符串转回数组

class Solution {
    public int[] plusOne(int[] digits) {
        if(digits[digits.length-1]<9)
        {
            digits[digits.length-1]+=1;
            return digits;
        }
        int number=0;
        for(int i=0;i<digits.length;i++)
        {
            number=10*number+digits[i];
        }
        number+=1;
        String s=new String();
        s=""+number;
        int[] res=new int[s.length()];
        for(int i=0;i<s.length();i++)
        {
            res[i]=(int)s.charAt(i)-(int)'0';
        }
        return res;
    }
}

但是遇到特别庞大的数组，int型就会溢出，这个时候就不能用这种思路。
直接的思路：

1. 如果是小于9的数字，直接加，break
2. 如果是9，改为0，flag进位改为0
3. 1、2循环
4. 判断第一位是不是要进位，要进则在0位加上1，这里本想用arrayList，但并不会用

class Solution {
    public int[] plusOne(int[] digits) {
        int flag=1;
        for(int i=1;i<=digits.length;i++)
        {
            if(digits[digits.length-i]<9)
            {
                digits[digits.length-i]+=1;
                flag=1;
                break;
            }
            else
            {
                digits[digits.length-i]=0;
                flag=0;
            }
        }
        
        if(flag==1)
            return digits;
        else
        {            
            int[] res=new int[digits.length+1];
            res[0]=1;
            for(int i=1;i<digits.length+1;i++)
            {
                res[i]=digits[i-1];
            }
            return res;
        }
    }
}

下面这个思路和我是一样一样的，但是并没有用到flag。
另一个比我好的地方是，我上面直接用9判断，只能适用于题目要求加1的题；如果换成+2，+3，我的代码就要大改动。这个计算的是和，更general。

public int[] plusOne(int[] digits) {
        int len = digits.length;
        for(int i = len-1; i >= 0; --i){
            digits[i] += 1;
            if(digits[i] != 10)
                return digits;
            else {
                digits[i] = 0;
                if (i == 0) {
                    int[] answer = new int[len + 1];
                    answer[0] = 1;
                    for (int j = 0; j < len; ++j) {
                        answer[j + 1] = digits[j];
                    }
                    return answer;
                }
            }
        }
        return digits;
    }

看了去年提交的代码，发现在最后需要给数组的第0位增加一个元素时用了System.arraycopy代替遍历。

//999...9的情况
            int[] result = new int[digits.length + 1];  
            result[0] = 1;  
            System.arraycopy(digits, 0, result, 1, digits.length);  
            return result;  

67. Add Binary
    https://leetcode.com/problems/add-binary/

和上一题数组的加法很像，这题是字符串的加法。但是感觉难度陡增？