LeetCode --- 字符串白胀、數(shù)組
簡(jiǎn)書(shū)專(zhuān)欄：http://www.reibang.com/nb/41796568
知乎專(zhuān)欄：https://zhuanlan.zhihu.com/c_174823416
一荞下、題目描述
來(lái)源：力扣（LeetCode）
給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)驳遵，在該數(shù)的基礎(chǔ)上加一气忠。
最高位數(shù)字存放在數(shù)組的首位蕉扮， 數(shù)組中每個(gè)元素只存儲(chǔ)單個(gè)數(shù)字菩浙。
你可以假設(shè)除了整數(shù) 0 之外彪笼，這個(gè)整數(shù)不會(huì)以零開(kāi)頭捧灰。
示例 :
輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入數(shù)組表示數(shù)字 123淆九。
輸入: [4,3,2,1]
輸出: [4,3,2,2]
解釋: 輸入數(shù)組表示數(shù)字 4321。
二毛俏、實(shí)現(xiàn)思路以及代碼
2.1 思路一：暴力破解法（不通過(guò)）
可以將數(shù)組轉(zhuǎn)換為整數(shù)炭庙，進(jìn)行加一然后再轉(zhuǎn)換成為數(shù)組。但是這樣做有一個(gè)缺陷煌寇，就是如果數(shù)組中的數(shù)超過(guò)了整數(shù)的范圍焕蹄，那么進(jìn)行轉(zhuǎn)換時(shí)會(huì)報(bào)錯(cuò)。有考慮過(guò)使用bigInteger但是那樣的話我覺(jué)得違背了題目想表達(dá)的含義阀溶。下面給出代碼：
public static int[] plusOne(int[] digits) {
int length = digits.length, temp = 0;
for(int i = length - 1; i >= 0; i--) {
temp += (digits[i] * Math.pow(10,length - i -1));
}
temp += 1;
String str = String.valueOf(temp);
String[] strs = str.split("");
int[] result = new int[strs.length];
for(int j = 0; j < str.length(); j++) {
result[j] = Integer.valueOf(strs[j]);
}
return result;
}
2.2 思路二：數(shù)組加一進(jìn)位法（巧妙）
理解題意可以發(fā)現(xiàn)腻脏，如果直接從數(shù)組入手鸦泳，當(dāng)最后一位不為9時(shí)，可以直接在數(shù)組最后一位上+1永品，然后返回?cái)?shù)組即可做鹰。所以要處理的就是當(dāng)最后一位為9時(shí)的情況。
模擬進(jìn)位操作鼎姐，從數(shù)組最后一位向前開(kāi)始遍歷钾麸，若digits[i] + 1之后取余10等于0，則表明進(jìn)位炕桨，繼續(xù)向前遍歷饭尝，進(jìn)行加一操作，并判斷取余10之后是否為0献宫，一直到不為0時(shí)表明該位置的數(shù)字加一之后不進(jìn)位芋肠，返回該數(shù)組
特殊情況是當(dāng)出現(xiàn)9，99遵蚜，999這類(lèi)數(shù)字時(shí)帖池，循環(huán)到底也不會(huì)返回，這是需要特殊處理一下吭净，擴(kuò)容一位睡汹，并令第一位為1即可
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >=0; i--) {
digits[i]++;
digits[i] %= 10;
if(digits[i] != 0) return digits;
}
digits = new int[digits.length+1];
digits[0] = 1;
return digits;
}
三、測(cè)試代碼
int[] nums1 = {6,5,4,3,2,1,0};
int[] nums2 = {6,5,4,3,2,9,9};
System.out.println(Arrays.toString(plusOne(nums1)));
System.out.println(Arrays.toString(plusOne(nums2)));
}
輸出結(jié)果為：
[6, 5, 4, 3, 2, 1, 1]
[6, 5, 4, 3, 3, 0, 0]
