给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。你可以假设这个整数不会以零开头。
仔细审题，会发现题干中给出了好几个预备条件。
（1）非空数组
（2）非负整数
（3）第一个数不会是0开头
数组元素的个数，就等于整数的位数。加一问题看似简单，直接在数组上操作却需要考虑情况多样的进位问题，有些复杂。因此不如先把数组转换成long/int，加一之后再重新转换回数组。
其中逻辑最复杂的部分，就是把int转换回数组的部分。需要循环取模。
此处的代码如果这样写，将无法应对位数增加的情况。比如输入9，加一之后位数+1，变成10。而遍历的循环变量边界还是以原始的9的长度为边界，因此结果一定是错误的。
循环处的i能够取的值，代表了会进行多少次循环。如果直接修改边界条件，会给所有的情况都增加一位数字。显然是有问题的。
从逻辑分析的角度上说，只能把这种特殊情况单独拎出来处理；或者有一种判断的方法，能够区分是否进位。
for (int i = 0; i < n ; i++) {
long t = (long) Math.pow(10, n - i - 1);
digits[i] = (int) (num / t % 10);
}
其实上面代码不能处理的情况，只有一种：位数加1的情况。而位数+1的情况，只会出现在所有位数都是9的情况下。因此就对这种情况做分离处理，代码如下：
while (c <= digits.length) {
int t = (int) (num / Math.pow(10, 1) % 10);
if (((int)(num / Math.pow(10, n - c - 1)) % 10 == 9)) {
c++;
continue;
} else if (c == n) {
result = new int[++n];
} else {
result = new int[n];
break;
}
}
但上面的做法最大的问题是，无法应对超长数组的转换。在基本类型中long已经是能够表示的最大的数。然而输入的数组却会轻而易举超过long能表示的极限，因此这个方法其实并不合适。
因此，如果我们直接对数组进行操作。正如上文所说，最复杂的情况出现在位数+1的时候。其余的进位情况，只是对该位的前一位+1即可。
进位只会出现在从末尾开始连续9出现的情况下。比如9,89,29,239,299。从末尾开始数，出现一个9则进一位，出现两个9则进两位。话句话说，这个数组中，只有数字9是特别的，并且必须是连续的9，比如989就只能算作出现了一个连续的9。
因此，可以写一个循环，从数组的末尾开始，寻找连续9的个数。如果是0个，直接末位数+1即可；如果是1个9，则出现9的位数变为0，它的前一位+1；如果是2个9，则末尾两位都变成0，前两位+1（比如99->100，或者799->800）。还需要确认的是，是否9的位数与数字本身的位数相等。
代码如下：
public int[] plusOne(int[] digits) {
int n = digits.length;
int count = 0;
int i = n - 1;
boolean flag = false;
int[] result;
// 统计连续9出现的次数
while (digits[i] == 9 && i>=0) {
count++;
i--;
}
// 判断位数与9出现的次数是否相等
if (count == n)
flag = true;
// 如果出现了全是9的情况，则位数+1
if (flag == true) {
result = new int[n+1];
result[0] = 1;
return result;
}
// 出现了几次9，就把末尾几位变为0，并把前一位进1
int count1 = count;
while (count > 0) {
digits[n - count] = 0;
count--;
}
// 如果count==0，则进行普通+1操作
digits[n-count1-1]++;
return digits;
}
以上代码的时间复杂度非常优秀，是我第一次写出执行时间1ms的代码。可见世界上不会有白花的功夫——虽然上一种解法失败了，却加深了我对本题的理解。因此才能逻辑清晰地写出第二种解答。
以上。
网友评论