Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.
You may assume the integer do not contain any leading zero, except the number 0 itself.
The digits are stored such that the most significant digit is at the head of the list.
用一个数组代表一个数字，求+1以后的值，数组返回形式。
加1以后两种情况：1、产生进位，高一位的数继续加1；2、没有进位，高位的数保持原样。
注意：99或999这样各位都是9的数，最后的结果会比原来的数多一位。
自己的思路是用out作为进位标志，如果一个循环结束，out还表示有进位，证明是99这样的情况，需要再增加一位。
public int[] plusOne(int[] digits) {
if (digits == null || digits.length == 0) {
int[] res = new int[1];
res[0] = 1;
return res;
}
List<Integer> list = new LinkedList<>();
boolean out = true;
for (int i = digits.length - 1; i >= 0; i--) {
if (out) {
if (digits[i] == 9) {
list.add(0, 0);
} else {
list.add(0, digits[i] + 1);
out = false;
}
} else {
list.add(0, digits[i]);
}
}
if (out) {
list.add(0, 1);
}
int[] res = new int[list.size()];
for (int i = 0; i < res.length; i++) {
res[i] = list.get(i);
}
return res;
}
自己用了一个list，所以空间复杂度是O(n)。翻看discuss，了解到自己处理的有些多余了，因为仅仅是99这样的情况会多一位，其他时候如果不产生进位，则直接修改传入的原数组再返回就可以了。
public int[] plusOne1(int[] digits) {
if (digits == null || digits.length == 0) {
return new int[]{1};
}
for (int i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits;
} else {
digits[i] = 0;
}
}
int[] res = new int[digits.length + 1];
res[0] = 1;
return res;
}