题目描述

给定一个数组表示非负整数，其高位在数组的前面，对这个整数加1，返回新数组。

我的解法——倒置后相加再倒置

先将数组倒置，后面加一个0，然后执行进位操作，然后再倒回来
n的复杂度。
结果：beat 42.78%

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        length = len(digits)
        
        for i in range(length/2):
            digits[i],digits[length - i - 1] = digits[length - i - 1],digits[i]
        digits.append(0)
        
        now = 1 # 当前位需要加的数
        i = 0
        while(i < length + 1 and now != 0):
            last = digits[i]
            digits[i] = (now + digits[i]) % 10
            if(now + last >= 10):
                now = (now + last) / 10
            else:
                now = 0
            i += 1
        
        if(digits[length] == 0):
            digits = digits[0:length]
        else:
           length += 1
           
        for i in range(length/2):
            digits[i],digits[length - i - 1] = digits[length - i - 1],digits[i]
    
        return digits

最优解法——直接相加

最好的解法！！！
直接相加，最后对第一位是否进位进行特判即可
n的时间复杂度

public int[] plusOne(int[] digits) {
    int carry = 1;
    for (int i = digits.length-1; i>= 0; i--) {
        digits[i] += carry;
        if (digits[i] <= 9) // early return 
            return digits;
        digits[i] = 0;
    }
    int[] ret = new int[digits.length+1];
    ret[0] = 1;
    return ret;
}