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