Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

Solution:

从最后一位开始，对每一位进行加一，然后判断进位，如果有进位就继续到下一位，否则就可以返回了。

如果到了最高位进位仍然存在，重新new一个数组，把第一个为赋成1（因为只是加一操作，其余位一定是0，否则不会进最高位）。
一次扫描，所以算法复杂度是O(n)，n是数组的长度。而空间上，一般情况是O(1)，但是如果数是全9，那么是最坏情况，需要O(n)的额外空间。

public class Solution {
    public int[] plusOne(int[] digits) {
        if(digits == null || digits.length == 0)
            return null;
        
        for(int i = digits.length - 1; i >= 0; i--) {
            if(digits[i] + 1 == 10) {
                digits[i] = 0;
            }else {
                digits[i] = digits[i] + 1;
                return digits;
            }
        }
        
        //deal with the carry of the first number
        int[] res = new int[digits.length + 1];
        res[0] = 1;  
        //no need to copy the rest elements in digits, 
        //because when we have carry at the first number, 
        //this means that rest numbers in digits are already 0 now.
        return res;
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/22365957

Follow up: Plus one，输入输出都是int，不能用＋和－

Bit operator
&: 都是1， ＝1
|: 有1， ＝ 1
^: 相同＝0， 不同＝1
~: 0->1, 1->0