66.加一

caution

原题链接：https://leetcode.cn/problems/plus-one/

思路

可以考虑从后往前进行操作，主要解决的问题是最后一位加 1 之后产生的进位问题，需要从后往前遍历数组：

• 如果 digits[i] + 1 == 10 了，说明要进位了，则指针需要往前移动一位（循环下次判断就可以判断这位是否加 1 大于 10）
• 如果 digits[i] + 1 小于 10，说明不需要进位，则到此结束为止。

有一种特殊情况，当 digits[0] 为 9 的时候，如果该位需要进位则数组长度会加 1，而且出现这种情况只有所有数都为 9 的时候出现，所以需要判断如果指针到达了数组的开头，那么说明数组长度需要加 1 并且除了第一个数是 1 其他都是 0。

核心思路：类似双指针的思路。

代码

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int sz = digits.size();
        if (digits.size() == 1) {
            if (digits[0] + 1 == 10) {
                digits.pop_back();
                digits.push_back(1);
                digits.push_back(0);
            } else {
                int t = digits[0];
                digits.pop_back();
                digits.push_back(t + 1);
            }
        } else {
            int i;
            for (i = digits.size() - 1; i >= 0;) {
                if (digits[i] + 1 == 10) {
                    digits[i] = (digits[i] + 1) % 10;
                    i--;
                } else {
                    digits[i] ++;
                    break;
                }
            }
            if (i == -1) {
                while (!digits.empty()) digits.pop_back();
                digits.push_back(1);
                for (int j = 1; j <= sz; j ++) digits.push_back(0);
            }
        }
        return digits;
    }
};