Palindrome Number

アルゴリズム概要

整数 x が 10 進表記で回文（左右対称）かどうかを判定します。

例1: x = 121  → true  (121は左右対称)
例2: x = -121 → false (負数は先頭に-が付く)
例3: x = 10   → false (01とは読めない)

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

Python実装

class Solution:
    def isPalindrome(self, x: int) -> bool:
        """
        整数 x が 10 進表記で回文かどうかを判定する。

        Args:
            x: 判定対象の整数（32bit 符号付き整数）

        Returns:
            x が 10 進表記で回文であれば True、そうでなければ False。

        Time Complexity: O(d)  （d は x の桁数 ≒ log10(|x|)）
        Space Complexity: O(1)  追加メモリは定数個の整数のみ。
        """
        # 負数、0 以外で末尾が 0 の数は回文にならない
        if x < 0 or (x % 10 == 0 and x != 0):
            return False

        # 0〜9 は 1 桁なので必ず回文
        if x < 10:
            return True

        rev: int = 0

        # 右半分を反転しつつ、左半分と比較できる状態まで進める
        # ループを抜ける条件:
        #   - 偶数桁: x と rev が同じ桁数になった時点で x <= rev
        #   - 奇数桁: 中央 1 桁を含んだ rev の方が 1 桁多くなった時点で x < rev
        while x > rev:
            digit: int = x % 10  # 末尾 1 桁を取得
            rev = rev * 10 + digit  # rev に桁を追加
            x //= 10  # 整数除算で末尾 1 桁を削除

        # 偶数桁: x == rev
        # 奇数桁: 中央 1 桁を無視するため、rev // 10 と比較
        return x == rev or x == rev // 10

フローチャート

フローの説明：
1. 基底条件で負数・末尾0・1桁数を早期判定
2. rev = 0 で初期化し、ループに入る
3. x > rev の間、右側の桁を反転して rev に積み上げる
4. 同時に x を縮小し、x <= rev になったらループ終了
5. 最後に x == rev または x == rev // 10 で回文判定
6. 左側の紫色の矢印でループバックし、次の反復へ進む

計算量分析