Plus One

Plus One – LeetCode 66

Problem

Description

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

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

The digits are stored such that the most significant digit is at the head of the list.

Answer

Original

Code

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

思路

使用在末尾加一然后，从尾至头传播进位。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$3$ ms，排名$88.57\%$

Better

思路

这题，这方法，够了。