Plus One

66. 加一

分析

从低位到高位进行加法，考虑进位
如果所有位数都发生进位（如 999 -> 1000），需要在最高位补 1

时间复杂度

时间复杂度 O(n)，遍历数组两次（反转 + 加法）

空间复杂度

空间复杂度 O(1)

C++代码

 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)
    {
      std::reverse(digits.begin(), digits.end());  // 反转数组，使低位在前
      int t = 1;  // 初始进位值为 1，即加 1

      for (int& x: digits)
      {
        t += x;   // 当前位加上进位
        x = t % 10;  // 更新当前位
        t /= 10;  // 计算新的进位
      }

      if (t)  // 最高位还有进位
        digits.push_back(t);

      std::reverse(digits.begin(), digits.end());  // 还原数组顺序
      return digits;
    }
};