Reverse Integer

アルゴリズム概要

問題

32bit符号付き整数 x の桁を反転し、結果が [-2³¹, 2³¹-1] の範囲外になる場合は 0 を返します。64bit整数の使用は禁止されています。

入出力例

Input: x = 123
Output: 321

Input: x = -123
Output: -321

Input: x = 120
Output: 21

Input: x = 2147483647
Output: 0 (範囲外)

制約

• -2³¹ ≤ x ≤ 2³¹-1
• 64bit整数は使用不可

戦略

• 文字列反転法: Pythonの高速な組み込み文字列処理を活用
• 符号分離: 絶対値を反転後に符号を掛け戻し
• 範囲チェック: 最後に32bit境界と比較
• 早期リターン: 1桁の場合は処理不要

主要ポイント

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

Python実装

from __future__ import annotations

class Solution:
    """
    Reverse Integer (LeetCode #7)
    32-bit 符号付き整数 x の数字を反転。範囲外は 0 を返す。
    """

    # 32bit境界定数（クラス定数として明示）
    INT_MAX: int = 2_147_483_647   #  2^31 - 1
    INT_MIN: int = -2_147_483_648  # -2^31

    def reverse(self, x: int) -> int:
        """
        文字列反転法による最速実装

        Args:
            x: 32-bit signed integer

        Returns:
            反転後の整数（範囲外は 0）

        Time: O(d), Space: O(d) — d は桁数（最大10）
        """
        # 基底条件: 1桁はそのまま返す（早期リターン）
        if -9 <= x <= 9:
            return x

        # 符号を分離して絶対値の文字列を反転
        sign: int = -1 if x < 0 else 1
        abs_x: int = -x if x < 0 else x

        # C実装の高速な文字列処理を活用
        # [::-1] スライスで反転、int() で整数化（先頭ゼロは自動削除）
        rev_abs: int = int(str(abs_x)[::-1])

        # 符号を適用
        result: int = rev_abs * sign

        # 32bit範囲チェック（Pythonの任意精度intを手動で拘束）
        if result < self.INT_MIN or result > self.INT_MAX:
            return 0

        return result

フローチャート

フローの説明：
1. 1桁判定で早期リターン（-9 ≤ x ≤ 9）
2. 符号を分離し、絶対値を文字列に変換
3. [::-1] で反転し、int() で整数化
4. 符号を適用して元の符号を復元
5. 32bit範囲チェックで範囲外なら 0 を返す
6. 範囲内なら result を返す

計算量分析

時間計算量: O(d)

• d は入力整数の桁数（最大10）
• str(), スライス [::-1], int() はすべて O(d)
• CPythonのC実装により、ループより高速

空間計算量: O(d)

• 文字列スライスで一時的に O(d) のメモリを使用
• 最終結果は整数1つ

手法比較