Zenn
🐧

#2:LeetCode-PalindromeNumber

に公開
Python
LeetCode
palindromenumber
tech

問題(翻訳)

整数 x が与えられたとき、それが 回文数（palindrome） かどうかを判定せよ。
回文数とは、整数を前から読んでも後ろから読んでも同じ数であるものを指す。

例: 121 は回文数 → true
例: -121 は回文数ではない（”-121” を逆に読むと “121-” になるため） → false
例: 10 は回文数ではない → false

制約

-2^{31} <= x <= 2^{31} - 1

解法

初めに思いついた解法

  • 方針
    • ナイーブで打開する
class Solution:
    def isPalindrome(self, x: int) -> bool:
        return str(x) == str(x)[::-1]
  • 時間計算量・空間計算量
    • 時間計算量：strでオブジェクトを生成でO(k)、逆順のコピーでO(k)になる
    • 空間計算量：str(x)とstr(x)[::-1]で生成しているため、こちらもO(k)となる

最終的な解法

  • 各桁数を見ていきながら、逆順の数値を作っていく
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x != 0 and x % 10 == 0):
            return False
        
        # これまで処理した桁を反転して積み上げた数値
        reversed_num = 0
        while x > reversed_num:
            reversed_num = reversed_num * 10 + x % 10
            x //= 10
            
        # 偶数桁の場合は純粋比較、奇数桁の場合は中央の値を落として比較
        return x == reversed_num or x == reversed_num // 10
  • 時間計算量・空間計算量
    • 時間計算量：桁数分見ていく必要があるのでO(k)は変わらず。途中で処理を止めるため約k/2回程度になるが、定数倍の改善でありO(log n)になるわけではない
    • 空間計算量：入力とreversed_numの定数分のデータのみ扱っているためO(1)となる

テストケース

s = Solution()

test_cases = [
    # (No, input, expected)
    (1, 121, True),
    (2, -121, False),
    (3, 10, False),
    (4, 0, True),
    (5, 1221, True),
    (6, 12321, True),
    (7, 123421, False),
    (8, 1001, True),
    (9, 1000021, False),
    (10, 2147447412, True),
]

for no, x, expected in test_cases:
    got = s.isPalindrome(x)
    assert got == expected, f"Test {no} failed: input={x}, expected={expected}, got={got}"

学び・気づき

  • 普通に算数を忘れていること笑
    • 桁操作の基本を思い出す必要があったこと(mod10で1の位を取り出す、//10で1桁落とす)、途中まで反転すれば十分だと気づいた
  • 文字列変換は便利だが計算量的には非効率

参考

GitHubで編集を提案

Discussion