Java和javascript如何實(shí)現(xiàn)給指定數(shù)加一

題目描述

給定一個(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。

解題方案

思路

• 標(biāo)簽：數(shù)組遍歷

• 這道題需要整理出來有哪幾種情況，在進(jìn)行處理會(huì)更舒服

1. 末位無進(jìn)位，則末位加一即可，因?yàn)槟┪粺o進(jìn)位，前面也不可能產(chǎn)生進(jìn)位，比如45 => 46

2. 末位有進(jìn)位，在中間位置進(jìn)位停止，則需要找到進(jìn)位的典型標(biāo)志，即為當(dāng)前位%10后為0，則前一位加1，直到不為0為止，比如499 => 500

3. 末位有進(jìn)位，并且一直進(jìn)位到最前方導(dǎo)致結(jié)果多出一位，對(duì)于這種情況，需要在第2種情況遍歷結(jié)束的基礎(chǔ)上，進(jìn)行單獨(dú)處理，比如999 => 1000

• 在下方的Java和JavaScript代碼中，對(duì)于第三種情況，對(duì)其他位進(jìn)行了賦值0處理，Java比較tricky直接new數(shù)組即可，JavaScript則使用了ES6語法進(jìn)行賦值

• 時(shí)間復(fù)雜度：O(n)

代碼

• Java版本

class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        for(int i = len - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] %= 10;
            if(digits[i]!=0)
                return digits;
        }
        digits = new int[len + 1];
        digits[0] = 1;
        return digits;
    }
}

• JavaScript版本

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    const len = digits.length;
    for(let i = len - 1; i >= 0; i--) {
        digits[i]++;
        digits[i] %= 10;
        if(digits[i]!=0)
            return digits;
    }
    digits = [...Array(len + 1)].map(_=>0);;
    digits[0] = 1;
    return digits;
};

畫解