Plus One

アルゴリズム概要

問題説明

大きな整数を配列形式で表現したとき（各要素が1桁、最上位桁が先頭）、この整数に1を加算した結果を配列で返す問題です。

入出力例

入力: digits = [1,2,3]
出力: [1,2,4]
説明: 123 + 1 = 124

入力: digits = [9,9,9]
出力: [1,0,0,0]
説明: 999 + 1 = 1000

入力: digits = [9]
出力: [1,0]
説明: 9 + 1 = 10

制約条件

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• 先頭に0を含まない（例: [0,1,2] は不正）

戦略

主要ポイント

ステップバイステップ解説

Python実装

class Solution:
    def plusOne(self, digits: list[int]) -> list[int]:
        """
        整数配列に1を加算する

        Time Complexity: O(n)
        Space Complexity: O(1) average, O(n) worst case
        """
        # 右から左へ走査
        for i in range(len(digits) - 1, -1, -1):
            # 現在の桁が9未満の場合
            if digits[i] < 9:
                digits[i] += 1
                return digits  # 繰り上がり不要、即座に返却

            # 現在の桁が9の場合、0にして繰り上がり継続
            digits[i] = 0

        # 全桁が9だった場合（例: [9,9,9] -> [1,0,0,0]）
        # 先頭に1を追加
        return [1, *digits]

TypeScript実装

function plusOne(digits: number[]): number[] {
    /**
     * 整数配列に1を加算する
     *
     * Time Complexity: O(n)
     * Space Complexity: O(1) average, O(n) worst case
     */

    // 右から左へ走査
    for (let i = digits.length - 1; i >= 0; i--) {
        // 現在の桁が9未満の場合
        if (digits[i] < 9) {
            digits[i]++;
            return digits;  // 繰り上がり不要、即座に返却
        }

        // 現在の桁が9の場合、0にして繰り上がり継続
        digits[i] = 0;
    }

    // 全桁が9だった場合（例: [9,9,9] -> [1,0,0,0]）
    // 先頭に1を追加
    return [1, ...digits];
}

フローチャート

フローの説明：
1. 右端のインデックス（i = len-1）から開始
2. i >= 0 の間ループを継続
3. digits[i] < 9 なら +1 して即座に終了（成功パス・緑）
4. digits[i] == 9 なら 0 に設定し、i を減らして次の桁へ（繰り上がり継続・紫）
5. ループを抜けた = 全桁が9 → 先頭に1を追加して終了（特殊ケースパス・赤）

計算量分析

最適化の比較