加一（非空数组）

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

 

示例 1：

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

示例 2：

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

示例 3：

输入：digits = [0]
输出：[1]

 

提示：

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

读题杀了我好多脑细胞。。。

官方给的思路，简直跟我想的一模一样：

当我们对数组 digitsdigits 加一时，我们只需要关注 digitsdigits 的末尾出现了多少个 99 即可。我们可以考虑如下的三种情况：

 

• 如果 digitsdigits 的末尾没有 99，例如 [1,2,3][1,2,3]，那么我们直接将末尾的数加一，得到 [1,2,4][1,2,4] 并返回；

• 如果 digitsdigits 的末尾有若干个 99，例如 [1,2,3,9,9][1,2,3,9,9]，那么我们只需要找出从末尾开始的第一个不为 99 的元素，即 33，将该元素加一，得到 [1,2,4,9,9][1,2,4,9,9]。随后将末尾的 99全部置零，得到 [1,2,4,0,0][1,2,4,0,0] 并返回。

• 如果 digitsdigits 的所有元素都是 99，例如 [9,9,9,9,9][9,9,9,9,9]，那么答案为 [1,0,0,0,0,0][1,0,0,0,0,0]。我们只需要构造一个长度比 digitsdigits 多 11 的新数组，将首元素置为 11，其余元素置为 00 即可。

对，于是我写出了： /** * Note: The returned array must be malloced, assume caller calls free(). */ int* plusOne(int* digits, int digitsSize, int* returnSize){ int j; if(digits[digitsSize-1]!=9){ digits[digitsSize-1]++; *returnSize=digitsSize; return digits;} else{for(int i=digitsSize-1;i>=0;i--) if(digits[i]!=9){ digits[i]++; if(j>i){ digits[j]=0;} *returnSize=digitsSize; return digits;} else{ int* temp=(int*)malloc(sizeof(int)*(digitsSize+1)); for(int i=1;i1;i++) temp[i]=0; temp[0]=1; *returnSize=digitsSize+1; return temp;} } }

和官方的思路完美契合，遗憾的是不能运行。。。

看一个妙人的代码，处处巧合，结果却没错：

 

int* plusOne(int* digits, int digitsSize, int* returnSize) { int jw = 1; int i; for (i = digitsSize - 1; i >= 0; i--) { digits[i] = digits[i] + jw; jw = digits[i] / 10; digits[i] = digits[i] % 10; } *returnSize = digitsSize + jw; int* sum = (int*)malloc(sizeof(int) * *returnSize); memset(sum, 0, sizeof(int) * *returnSize); for (i = digitsSize - 1; i >= 0; i--) { sum[i + jw] = digits[i]; } sum[0] += jw; return sum; }

这个代码除了不是我写的，真的太完美了。🥹

 

看题，突破点在于数字是不是9，最后一位开始往前遍历，如果遇到9，就将此位换为0，继续往前遍历，遇到的第一个非9的数字，加一即可返回。如果数组的所有元素都是9，遇不到非9数字，就直接开辟一个新数组，第一位放1，后面直接放0返回新数组。

所以这个题不同输入可能会有不同的返回途径。

 

/** * Note: The returned array must be malloced, assume caller calls free(). */ int* plusOne(int* digits, int digitsSize, int* returnSize){ for (int i = digitsSize - 1; i >= 0; i--) { if (digits[i] != 9) { //遇到非9，即可返回 digits[i] ++; *returnSize = digitsSize; return digits; //直接返回 } else digits[i] = 0; //如果当前元素为9，那么加1之后会变0 } *returnSize = digitsSize+1; //没遇到非9，元素都是9，另一条路径返回 int *temp = (int *)malloc(sizeof(int) * (digitsSize+1)); for(int i = 1; i < digitsSize + 1; i++) temp[i] = 0; temp[0] = 1; //新数组长度加1，并第一个元素置赋值为1 return temp; } 好像这块的题目已经把动态规划常规使用了，已经有点熟练了。

再回头看我第一个代码，说实话，有点幼稚😓

真厉害👍