[每日 LeetCode] 66. Plus One

Description:

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

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

Example 2:

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

思路：本题要求在有序数组的最后加 1，加 1 后的效果如正常的数字相加需要考虑进位。主要考虑最后一个数字是否为 9，若不为 9 则直接 +1，若为 9，需要考虑—+1 后进位和不进位两种情况。

C++ 代码

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for(int i = digits.size() - 1; i >= 0; i--)   
        {
            if(digits[i] != 9)
            {
                digits[i] ++;
                break;
            }
            digits[i] = 0;
        }
        if(digits[0] == 0)
            digits.insert(digits.begin(), 1);
        return digits;
    }
};
​

运行时间：12ms

运行内存：8.4M