Add One

给定一个非负数,表示一个数字数组,在该数的基础上+1,返回一个新的数组。

该数字按照大小进行排列,最大的数在列表的最前面。

样例

给定 [1,2,3] 表示 123, 返回 [1,2,4].
给定 [9,9,9] 表示 999, 返回 [1,0,0,0].

Solution

先翻转,然后逐个加,最后再翻转,注意最后的进位

Complexity

时间复杂度 O(n),空间复杂度 O(1)

Code

public class Solution {
    public int[] plusOne(int[] digits) {
        if (digits.length == 0) return digits;
        int carry = 1;
        for (int i = digits.length - 1; i >= 0; --i) {
            digits[i] += carry;
            carry = digits[i] / 10;
            digits[i] = digits[i] % 10;
        }
        if (carry == 0) return digits;
        int[] res = new int[digits.length + 1];
        res[0] = carry;
        System.arraycopy(digits, 0, res, 1, digits.length);
        return res;
    }
}

class Solution:
    # @param {int[]} digits a number represented as an array of digits
    # @return {int[]} the result
    def plusOne(self, digits):
        # Write your code here
        l = len(digits)
        addit = 1
        digits.reverse()
        ans = []
        for i in range(l):
            if digits[i] + addit == 10:
                ans.append(0)
                addit = 1
            else:
                ans.append(digits[i] + addit)
                addit = 0
        if addit == 1:
            ans.append(1)
        ans.reverse()
        return ans