给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
很明显，这道题需要考虑 9+1=10，即类似于“进位”的情况。我一开始想的一种较笨的算法：
public static int[] plusOne(int[] digits) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < digits.length; i++) {
list.add(digits[i]);
}
Collections.reverse(list);
boolean isContinue = true;
for (int i = 0; i < list.size(); i++) {
if (isContinue) {
if ((list.get(i) + 1) > 9) {
list.set(i, 0);
if (i + 1 == list.size()) {
list.add(1);
isContinue = false;
} else {
isContinue = true;
}
} else {
list.set(i, list.get(i) + 1);
isContinue = false;
}
}
}
Collections.reverse(list);
int[] arrNew = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
arrNew[i] = list.get(i);
}
return arrNew;
}
参考别人的的算法：
public static int[] plusOne2(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
int[] res = new int[digits.length + 1];
res[0] = 1;
return res;
}
注意一个关键的细节，就是当你 new 一个int[] 后，每一个数组元素初始值皆为 0，这刚好符合这道题中遇到需要“进位”的情况，第二种算法正好利用了这一特点。
