题目链接：Plus One

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

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

这道题的要求是给定一个数组表示非负整数，其高位在数组的前面，对这个整数加1。

简单的大数加法，遍历数组的每位，同时处理进位，如果最后还有进位，则在数组最前面在插入1即可。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution
{
public:
    vector<int> plusOne(vector<int> &digits)
    {
        int c = 1; // 令进位标识初始值为1
        for(int i = digits.size() - 1; i >= 0; -- i)
        {
            // 不断处理进位
            int a = digits[i] + c;
            digits[i] = a % 10;
            c = a / 10;
        }
        // 如果最后还有进位，则在数组最前面在插入1
        if(c == 1)
            digits.insert(digits.begin(), 1);
        
        return digits;
    }
};

当然，由于这题是比较特殊的大数处理，只有从低位开始全是9，才会不断产生进位，而且进位后数字为0。当且仅当说有数位全是9的时候，才会多进出1位，此时最高位是1，其他所有位全是0（由于多出1位，因此需要在最后添加1个0）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution
{
public:
    vector<int> plusOne(vector<int> &digits)
    {
        // 从后往前，碰到第一个不是9的就对其加1，然后返回即可
        for(int i = digits.size() - 1; i >= 0; -- i)
        {
            if(digits[i] == 9)
                digits[i] = 0;
            else
            {
                ++ digits[i];
                return digits;
            }
        }
        // 最高位改成1，最后再添加个0
        digits[0] = 1;
        digits.push_back(0);
        return digits;
    }
};