加一-66

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

示例 2：

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

示例 3：

Input: digits = [0]
Output: [1]

提示：

• 1 ≤ digits.length ≤ 100；
• 0 ≤ digits[i] ≤ 9；

思路

反向遍历数组digits，依次取元素加一，可能会出现以下三种情况：

• 末尾数字非9：末尾加一，前面所有数字保持不变；
• 仅末尾数字是9：末尾加一后，到位置i进位停止，digits[i]加一，digits[i+1]到digits[digits.len()]-1全部置0；
• 全部数字是9：新建一个数组nums，长度为digits.len()+1，除nums[0]为1外，其他元素全部置0；

代码

Rust：

// 0ms, 1.9MB
impl Solution {
    pub fn plus_one(mut digits: Vec<i32>) -> Vec<i32> {
        let mut index = digits.len() - 1;
        loop {
            if digits[index] < 9 {
                digits[index] += 1;
                return digits;
            }
            digits[index] = 0;
            if index > 0 {
                index -= 1;
            } else if index == 0 {
                break;
            }
        }
        digits = vec![0; digits.len() + 1];
        digits[0] = 1;
        return digits;
    }
}