66.md

66. 加一

输入: [1,2,3]
输出: [1,2,4]

思路

• 标签：数组
• 题目大意跟 2. 两数相加 差不多
• 可操作原数组，不使用额外空间
• 从后往前遍历，如果小于 9，将数组元素加 1，如果等于 9，将当前变为 0，下一位加 1（进位）
• 需要考虑 99 变 100 的情况，此时数组长度需要加 1（Python 可利用 insert 将数组长度加 1）
• 时间复杂度：O(n)。最多需要遍历 n 次
• 空间复杂度：O(1)。不需要额外空间

  9 8 7 6
  <-------
  9 8 7 7

  8 9 9 9
  <-------
  9 0 0 0 

  9 9 9 9
  <-------
1 0 0 0 0 

代码

## Python3
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in reversed(range(len(digits))):
            if digits[i] < 9:
                digits[i] = digits[i] + 1
                return digits
            else:
                digits[i] = 0
        digits.insert(0, 1) # Python 可利用 insert 将数组长度加 1
        return digits

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

测试用例

输入	输出
[9]	[1, 0]
[9, 9]	[1, 0, 0]
[8,9,9,9]	[9,0,0,0]