66. Plus One

66. Plus One

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

该题目要求：将一整数按位存储在vector中，对其实现+1操作，返回结果.
对存储序列vector中元素，倒序遍历，末位+1，若<10可直接返回，否则，保存进位加之到下一位，循环至最高位.
若此时，进位依然为1，则新建长度增一的vector首位为1，其余为0，返回即可.

(O(n)) time, (O(1)) space.
他人思路, 自己的代码:

vector<int> plusOne(vector<int>& A) {
    int n = A.size();
    if (A[n - 1] + 1 < 10) {
        A[n - 1] += 1;
        return A;
    } else A[n - 1] = 0;

    //最后一位有为10
    int i;
    for (i = n - 2; i >= 0; i--) {
        A[i] += 1; //倒数第二位+1
        if (A[i] == 10) A[i] = 0;
        else return A;
    }

    // 若循环执行完，仍没return，
    // 则另建一个vector，长度为n+1，首位为１，其余n为为０，并返回
    vector<int> B;
    B.push_back(1);
    for (i = 0; i < n; i++)
        B.push_back(0);
    return B;
}

人家更牛逼的代码:

vector<int> plusOne(vector<int> &digits) {
    int n = digits.size();
    for (int i = n - 1; i >= 0; --i) {
        if (digits[i] == 9) digits[i] = 0;
        else {
            digits[i]++;
            return digits;
        }
    }

    // 很牛逼的样子
    digits[0] = 1;
    digits.push_back(0);
    return digits;
}