給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)光坝，在該數(shù)的基礎(chǔ)上加一。
最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個(gè)元素只存儲(chǔ)一個(gè)數(shù)字糠惫。
你可以假設(shè)除了整數(shù) 0 之外，這個(gè)整數(shù)不會(huì)以零開頭钉疫。
示例 1:
輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入數(shù)組表示數(shù)字 123硼讽。
示例 2:
輸入: [4,3,2,1]
輸出: [4,3,2,2]
解釋: 輸入數(shù)組表示數(shù)字 4321。
很明顯牲阁，這道題需要考慮 9+1=10固阁，即類似于“進(jìn)位”的情況。我一開始想的一種較笨的算法：
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;
}
注意一個(gè)關(guān)鍵的細(xì)節(jié)城菊，就是當(dāng)你 new 一個(gè)int[] 后备燃，每一個(gè)數(shù)組元素初始值皆為 0，這剛好符合這道題中遇到需要“進(jìn)位”的情況役电，第二種算法正好利用了這一特點(diǎn)赚爵。
