66.加一
#数组 2024-08-08 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        bool flag = true;   // 存在进位
        vector<int> data;
        if(digits[digits.size() - 1] + 1 != 10){    // 如果加1不会进位，返回最后一个元素加1的原数组
            digits[digits.size() - 1]++;
            return digits;
        }

        for(int i = digits.size() - 1; i >= 0; i--){
            if(flag){
                if(digits[i] + 1 != 10){    // 后续不会有进位，flag = false;
                    data.push_back(digits[i] + 1);
                    flag = false;
                }else{  // 后续还有进位，flag保持不变
                    data.push_back(0);
                }
            }else{  // 没有进位，添加原数组元素即可
                data.push_back(digits[i]);
            }
        }
        if(flag){   // 如果有进位，代表这个数是 N 个 9组成，所以添加元素 1
            data.push_back(1);
        }
        reverse(data.begin(),data.end());   // 反转
        return data;
    }
};

这道题容易让人误解，应该把题意讲得清楚些。有一个自然数，被拆分成个位数存储在数组中，对这个自然数进行加 1 操作。很明显，如果我们的自然是99，那么加 1 的结果就是 100，显然原数组是存储不下的，因为vector容器不支持头部插入元素。

如果数组中的末尾元素 加 1 之后不存在进位，只需要把原数组的末尾元素加 1 之后返回即可。

如果存在进位，就需要声明一个新的容器 data 来存储元素，避免原数组因为进位操作导致无法存储超过原长度的元素个数。基于存在进位的这种情况开始对原数组进行计算，第一次进入 for 循环中肯定是存在进位的情况。如果当前元素加 1 依旧满足进位，那么 flag 保持不变，添加元素 0 到 data 容器中。如果当前元素 加 1 不满足进位，flag 设置为 false，添加当前元素 加 1 之后的结果到 data容器中。

前面讲，进入 for 循环的第一次必然存在进位，那么此后就会出现两种情况：如果 flag 为 false ，后续的原数组元素添加到 data 容器中即可。如果 flag 依旧为 true，那不过是重复上面的逻辑，直到 flag 为 false 才进入到”原数组元素添加到 data 容器中即可“阶段。

如果 flag 始终为 true ，那么还需要添加元素 1 到 data 容器中。假定自然数为99，那么上面的逻辑执行下来，数组中存储的元素是 0 0。所以，如果 flag 依旧为 true，我们需要继续添加 元素 1 进来，否则不进行新的元素添加。然后就可以 data 容器反转之后进行返回，得到符合题意的结果。