题目链接

题目描述

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

示例

示例1：

输入：digits = [1,2,3] 输出：[1,2,4] 解释：输入数组表示数字 123。

提示

  • 1 <= digits.length <= 100

  • 0 <= digits[i] <= 9

    思路

    数学：分类讨论

    某个数加一有两种情况：进位或者不进位。

  • 不进位，则将该位数字加一，返回答案。

  • 进位，该位置0，高位加一

特殊情况，如99,999…，所有位都进位，置0后变为00,000…，此时只需要在开头添加一位1即可。

题解

  1. class Solution {
  2.    public:
  3.     vector<int> plusOne(vector<int>& digits) {
  4.         for (int i = digits.size() - 1; i >= 0; --i) {
  5.             if (9 == digits[i]) {
  6.                 digits[i] = 0;
  7.             } else {
  8.                 digits[i]++;
  9.                 return digits;
  10.             }
  11.         }
  12.         digits.insert(digits.begin(), 1);
  13.         return digits;
  14.     }
  15. };

复杂度分析

  • 时间复杂度：0066-加一 - 图1
  • 空间复杂度：0066-加一 - 图2