每日一道 LeetCode (14)：數(shù)組加一
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉(cāng)庫(kù)
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：數(shù)組加一
題目來(lái)源：https://leetcode-cn.com/problems/plus-one/
給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。
最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個(gè)元素只存儲(chǔ)單個(gè)數(shù)字。
你可以假設(shè)除了整數(shù) 0 之外，這個(gè)整數(shù)不會(huì)以零開(kāi)頭。
示例?1:
輸入:?[1,2,3]
輸出:?[1,2,4]
解釋:?輸入數(shù)組表示數(shù)字 123。
示例?2:
輸入:?[4,3,2,1]
輸出:?[4,3,2,2]
解釋:?輸入數(shù)組表示數(shù)字 4321。
解題思路
這道題看完以后，感覺(jué)好像很簡(jiǎn)單的樣子， LeetCode 最近幾天的題讓我一下感覺(jué)自己智商又在線了，甚至有了能暴打 LeetCode 的幻覺(jué)。
先說(shuō)下我的思路，整個(gè)數(shù)組取到最后一位，直接 +1 返回，這不完了么？
感覺(jué)自己又能小母牛倒立了。
結(jié)果我第一次代碼寫(xiě)完，這個(gè)世界充滿了惡意，把我的臉又一次的按在了地上摩擦。
最開(kāi)始的代碼是這個(gè)樣子的：
public?int[]?plusOne(int[]?digits)?{
????digits[digits.length?-?1]?+=?1;
????return?digits;
}
上面的代碼沒(méi)有問(wèn)題，可惜沒(méi)有考慮 9 ， 99 ， 999 這種進(jìn)位的情況。
這就很尷尬了，因?yàn)閭魅氲慕Y(jié)構(gòu)是數(shù)組，傳出的結(jié)構(gòu)也是數(shù)組，總所周知，數(shù)組是不能動(dòng)態(tài)擴(kuò)容的，這就意味著如果產(chǎn)生了進(jìn)位我們需要一個(gè)新的數(shù)組。
而且我們還需要在計(jì)算的時(shí)候進(jìn)行判斷，判斷當(dāng)前的計(jì)算是否產(chǎn)生了進(jìn)位。
判斷進(jìn)位在前面的文章中介紹過(guò)，很簡(jiǎn)單，我們直接取余數(shù)判斷余數(shù)是否為 0 就可以了，如果余數(shù)為0 那么一定產(chǎn)生了進(jìn)位。
如果整個(gè)數(shù)組的余數(shù)全都變成了 0 ，如 0 ， 00 ， 000 ，那么傳入的數(shù)組一定是 9 ， 99 ， 999 這種，這時(shí)候我們搞個(gè)新的數(shù)組，直接把開(kāi)頭賦值成 1 ，剩余位數(shù)全是 0 ，返回就可以了。
代碼實(shí)現(xiàn)
上面已經(jīng)把思路說(shuō)的很清晰了，下面是我寫(xiě)的代碼：
public?int[]?plusOne(int[]?digits)?{
????//?從末尾開(kāi)始循環(huán)
????for?(int?i?=?digits.length?-?1;?i?>=?0;?i--)?{
????????//?先?+1
????????digits[i]++;
????????//?取余數(shù)，?10?的余數(shù)為?0
????????digits[i]?=?digits[i]?%?10;
????????//?判斷余數(shù)是否為?0?，如果為?0?則再循環(huán)一次，產(chǎn)生了進(jìn)位，不為?0?則可以直接返回
????????if?(digits[i]?!=?0)?return?digits;
????}
????//?如果在上面的循環(huán)未返回，則整體產(chǎn)生進(jìn)位，類(lèi)似于?9?，?99?，?999?，?9999?這種數(shù)組
????digits?=?new?int[digits.length?+?1];
????digits[0]?=?1;
????return?digits;
}
注釋標(biāo)記的很明確了，稍微有點(diǎn)反人類(lèi)的就是這個(gè)循環(huán)是倒序循環(huán)，從最后一位開(kāi)始往前循環(huán)。好像最近的題使用到的都是倒序循環(huán)。
數(shù)組操作的效率是極其高效的，而且我發(fā)現(xiàn)，但凡是使用數(shù)組操作，在 LeetCode 上基本耗時(shí)都是 0ms 。
