66. Plus One

題目敘述

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits does not contain any leading 0's.

題目翻譯

這題目就是要把陣列 digits 當作數值，從個位數加上一後的結果。

解法解析

這題大概有三種解法，前兩種我覺得是類似的，就是將其轉換成數值來處理，然後再轉換回陣列。第一種是轉換成數值，另一種是反轉相加後再反轉。第三種就是我範例所使用，從尾數判斷。因為需要進位的情況只有在其值為 9 的情況，所以只有這種情境需要做處理，其他就只要單純的加一就好了。

解法範例

Go

func plusOne(digits []int) []int {
    var n int = len(digits)

    for i := n - 1; i >= 0; i-- {
        if digits[i] < 9 {
            digits[i]++
            return digits
        }
        digits[i] = 0
    }

    return append([]int{1}, digits...)
}

JavaScript

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    const n = digits.length;

    for (let i = n - 1; i >= 0; i--) {
        if (digits[i] === 9) {
            digits[i] = 0;
        } else {
            digits[i]++;
            return digits;
        }
    }

    return [1, ...digits];
};

Kotlin

class Solution {
    fun plusOne(digits: IntArray): IntArray {
        var n = digits.size

        for (i in n - 1 downTo 0) {
            if (digits[i] < 9) {
                digits[i]++
                return digits
            }
            digits[i] = 0
        }

        return intArrayOf(1) + digits
    }
}

PHP

class Solution
{

    /**
     * @param Integer[] $digits
     * @return Integer[]
     */
    function plusOne($digits)
    {
        $n = count($digits);

        for ($i = $n - 1; $i >= 0; $i--) {
            if ($digits[$i] < 9) {
                $digits[$i]++;
                return $digits;
            }
            $digits[$i] = 0;
        }

        return array_merge([1], $digits);
    }
}

Python

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)

        # move along the input array starting from the end
        for i in range(n - 1, -1, -1):
            # set all the nines at the end of array to zeros
            if digits[i] == 9:
                digits[i] = 0
            # here we have the rightmost not-nine
            else:
                # increase this rightmost not-nine by 1
                digits[i] += 1
                # and the job is done
                return digits

        # we're here because all the digits are nines
        return [1] + digits

Rust

Swift

class Solution {
    func plusOne(_ digits: [Int]) -> [Int] {
        var n = digits.count
        var digits = digits

        for i in (0..<n).reversed() {
            if digits[i] < 9 {
                digits[i] += 1
                return digits
            }
            digits[i] = 0
        }

        return [1] + digits
    }
}