LeetCode 66. 加一數(shù)組進(jìn)位處理詳解 Java/Python 實(shí)現(xiàn)題目鏈接66. 加一 - 力扣LeetCode題目描述給定一個(gè)表示大整數(shù)的整數(shù)數(shù)組digits其中digits[i]是整數(shù)的第i位數(shù)字。這些數(shù)字按從左到右從最高位到最低位排列。這個(gè)大整數(shù)不包含任何前導(dǎo)0。將大整數(shù)加1并返回結(jié)果的數(shù)字?jǐn)?shù)組。示例示例 1輸入digits [1,2,3] 輸出[1,2,4] 解釋輸入數(shù)組表示數(shù)字 123。 加 1 后得到 123 1 124。 因此結(jié)果應(yīng)該是 [1,2,4]。示例 2輸入digits [4,3,2,1] 輸出[4,3,2,2] 解釋輸入數(shù)組表示數(shù)字 4321。 加 1 后得到 4321 1 4322。 因此結(jié)果應(yīng)該是 [4,3,2,2]。示例 3輸入digits [9] 輸出[1,0] 解釋輸入數(shù)組表示數(shù)字 9。 加 1 得到了 9 1 10。 因此結(jié)果應(yīng)該是 [1,0]。提示1 digits.length 1000 digits[i] 9digits不包含任何前導(dǎo)0解題思路這道題的核心是模擬數(shù)字加法的進(jìn)位過程。我們需要從最低位數(shù)組末尾開始逐位加 1處理可能出現(xiàn)的進(jìn)位。關(guān)鍵點(diǎn)分析從右往左遍歷因?yàn)榧?1 操作從最低位開始所以要從數(shù)組末尾開始遍歷。遇到非 9 的數(shù)字直接加 1 并返回因?yàn)椴粫?huì)產(chǎn)生進(jìn)位。遇到 9將當(dāng)前位設(shè)為 0繼續(xù)向前遍歷因?yàn)樾枰M(jìn)位。全是 9 的情況如果遍歷完所有位都是 9說明需要增加一位新數(shù)組長(zhǎng)度為digits.length 1首位為 1其余位為 0。舉例說明例子 1digits [1,2,3]從末尾開始index 2digits[2] 3不是 9加 1 變成 4返回[1,2,4]。例子 2digits [1,9,9]index 2digits[2] 9設(shè)為 0。index 1digits[1] 9設(shè)為 0。index 0digits[0] 1不是 9加 1 變成 2返回[2,0,0]。例子 3digits [9,9,9]index 2digits[2] 9設(shè)為 0。index 1digits[1] 9設(shè)為 0。index 0digits[0] 9設(shè)為 0。循環(huán)結(jié)束創(chuàng)建新數(shù)組[1,0,0,0]返回。代碼實(shí)現(xiàn)Java 最優(yōu)寫法推薦classSolution{publicint[]plusOne(int[]digits){for(intindexdigits.length-1;index0;index--){if(digits[index]!9){digits[index]1;returndigits;}digits[index]0;}int[]newArrnewint[digits.length1];newArr[0]1;returnnewArr;}}Python 版本classSolution(object):defplusOne(self,digits): :type digits: List[int] :rtype: List[int] indexlen(digits)-1whileindex0:ifdigits[index]!9:digits[index]1returndigits digits[index]0index-1digits.insert(0,1)returndigits代碼說明Java 版本從末尾開始遍歷for (int index digits.length - 1; index 0; index--)。遇到非 9 的數(shù)字if(digits[index]!9){digits[index]1;returndigits;}直接加 1 并返回因?yàn)椴粫?huì)產(chǎn)生進(jìn)位后面的高位不需要改變。遇到 9digits[index]0;當(dāng)前位設(shè)為 0繼續(xù)向前遍歷處理進(jìn)位。循環(huán)結(jié)束仍未返回說明所有位都是 9例如[9,9,9]。此時(shí)需要int[]newArrnewint[digits.length1];newArr[0]1;returnnewArr;創(chuàng)建新數(shù)組長(zhǎng)度為原長(zhǎng)度加 1首位為 1其余位默認(rèn)為 0。Python 版本Python 版本思路與 Java 版本完全一致只是語法不同使用while循環(huán)代替for循環(huán)。使用digits.insert(0, 1)在列表頭部插入元素 1這比 Java 創(chuàng)建新數(shù)組更簡(jiǎn)潔。復(fù)雜度分析時(shí)間復(fù)雜度O(n)最壞情況下需要遍歷整個(gè)數(shù)組全是 9 的情況。空間復(fù)雜度O(1)除了全是 9 的情況需要?jiǎng)?chuàng)建數(shù)組外其余情況都是原地修改。即使創(chuàng)建新數(shù)組空間復(fù)雜度也是O(n)但這是必要的。常見錯(cuò)誤寫法分析有些同學(xué)可能會(huì)寫出下面這樣的代碼publicint[]plusOne(int[]digits){for(intindexdigits.length-1;index0;index--){intcdigits[index];if(index0c9){// return1returndigitals;// 錯(cuò)誤變量名寫錯(cuò)應(yīng)該是 digits}if(c!9){// return2returndigits;// 錯(cuò)誤這里沒有加 1}else{digits[index]0;}}// 語法兜底邏輯永遠(yuǎn)執(zhí)行不到returndigits;}這段代碼存在幾個(gè)問題變量名拼寫錯(cuò)誤digitals應(yīng)該是digits。邏輯錯(cuò)誤在c ! 9的分支中直接返回了digits但沒有執(zhí)行digits[index] 1操作。這樣即使遇到非 9 的數(shù)字也不會(huì)加 1。特殊情況處理不當(dāng)當(dāng)index 0 c 9時(shí)應(yīng)該創(chuàng)建新數(shù)組返回但代碼只是返回了原數(shù)組沒有處理進(jìn)位。正確思路對(duì)比最優(yōu)寫法之所以簡(jiǎn)潔是因?yàn)樗プ×藛栴}的本質(zhì)遇到非 9 就加 1 返回這是最常見的情況直接處理。遇到 9 就設(shè)為 0 繼續(xù)處理進(jìn)位。循環(huán)結(jié)束仍未返回說明全是 9需要擴(kuò)展數(shù)組。這種寫法不需要額外的變量也不需要特殊的邊界判斷邏輯非常清晰。Java 和 Python 實(shí)現(xiàn)對(duì)比Java 的特點(diǎn)數(shù)組長(zhǎng)度固定需要?jiǎng)?chuàng)建新數(shù)組來處理全 9 的情況。使用for循環(huán)語法更緊湊。返回值類型是int[]。Python 的特點(diǎn)列表是動(dòng)態(tài)的可以使用insert方法在頭部插入元素。使用while循環(huán)控制更靈活。返回值類型是List[int]。共同點(diǎn)兩者的核心邏輯完全一致從右往左遍歷非 9 加 1 返回9 設(shè)為 0 繼續(xù)全 9 處理進(jìn)位總結(jié)這道題雖然簡(jiǎn)單但很好地考察了對(duì)數(shù)組操作和進(jìn)位處理的理解。核心要點(diǎn)從右往左遍歷模擬加法的進(jìn)位過程。遇到非 9 直接加 1 返回這是最普遍的情況。遇到 9 設(shè)為 0 繼續(xù)處理進(jìn)位。全是 9 的特殊情況需要?jiǎng)?chuàng)建新數(shù)組長(zhǎng)度為原長(zhǎng)度加 1首位為 1。關(guān)鍵點(diǎn)回顧遍歷方向從數(shù)組末尾到開頭非 9 處理digits[index] 1; return digits;9 的處理digits[index] 0;全 9 處理創(chuàng)建新數(shù)組首位為 1Java或insert(0, 1)Python這道題的思路也可以擴(kuò)展到其他進(jìn)位相關(guān)的題目比如字符串相加、二進(jìn)制加法等。掌握這個(gè)模板對(duì)解決類似問題很有幫助。