题目

中文

image.png

英文

Given a non-empty array of digits representing a non-negative integer, increment one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.

represent v代表
non-negative adj 非负数的
increment n. 增加
element n 元素
the most significant digit 最高有效数字
not contain any leading zero 不以0打头

题解

第一次

思路

简单看来 直接加就好，但是重点是考虑进位，如果进位则前面加一 后面置0
全为9长度加一 （提前预判）因为无动态数组

  1. int *plusOne(int *digits, int digitsSize, int *returnSize)
  2. {
  3.     for (int i = digitsSize-1; i >= 0; i--)
  4.     {
  5.         if (digits[i] == 9)
  6.             digits[i] = 0;
  7.         else
  8.         {
  9.             digits[i]++;
  10.             *returnSize = digitsSize;
  11.             return digits;
  12.         }
  13.     }
  15.     int *result = (int *)malloc(sizeof(int) * (digitsSize + 1));
  16.     memset(result, 0, (digitsSize + 1) * sizeof(int));
  17.     result[0] = 1;
  18.     *returnSize = digitsSize + 1;
  19.     return result;
  20. }

从数组尾开始 如果是9 则赋值0
如果不是9 则该位加1 并赋值returnSize 返回digits
到循环结束后 如果未结束 则代表首位进位 使用result作为大一号数组
第一位1 其他都0 返回即可
时间复杂度 O(N)

扩展

看其他人题解 基本都是这个 应该也可以用栈 但吃力不讨好。

void plusone(vector<int> &digits)
{
    int n = digits.size();
    for (int i = n - 1; i >= 0; --i)
    {
        if (digits[i] == 9)
        {
            digits[i] = 0;
        }
        else
        {
            digits[i]++;
            return;
        }
    }
        digits[0] =1;
        digits.push_back(0);

}

可以学习一下动态数组