LeetCode解説　一日一問　9.Palindrome Number

LeetCodeって？
問題
回答
1. 数値のまま扱う方法
  1. 結果
2. 文字列に変換する方法
  1. 結果

LeetCodeって？

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。

2022年12月現在2,000問を超える問題が登録されています。

各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。

正誤判定は自動で行われます。

使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。

私はPython3で解いています。

問題

Palindrome Number - LeetCode

Can you solve this real interview question? Palindrome Number - Given an integer x, return true if x is a palindrome, and false otherwise. Example 1: Inpu...

タイトル：9. Palindrome Number

難易度：Easy

内容：

整数 x が与えられる。x が回文である場合Trueを、それ以外はFalseを返す。

例：

Input: x = 121
Output: true

Input: x = -121
Output: false
※ - が入る場合回文とはしない

Input: x = 10
Output: false

回答

x を数値のまま扱う方法と、文字列にしてしまう方法があります。後者のほうがはるかに楽ですがどっちも作ってみます。

数値のまま扱う方法

一番上位の桁と一番下位の桁を取り出し比較、同じ数値であれば二番目の上位桁と下位桁を比較を繰り返します。

R = int(x % 10 ** (i + 1) / (10 ** i)) が下位側の数値の抽出
L = int(x / (10 ** (digit – 1 – i))) が上位側の数値の抽出です。

# 数値のまま扱う
import math
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 : return False # 負の数は除外
        if x < 10 : return True # 一桁の数値は無条件でTrue

        digit = int(math.log10(x)) + 1 # xの桁数

        # 桁数が偶数の場合桁数の半分、奇数の場合（桁数-1）の半分ループ
        for i in range(digit // 2):
            R = int(x % 10 ** (i + 1) / (10 ** i)) # 桁数の小さい側の値
            L = int(x / (10 ** (digit - 1 - i))) % 10 # 桁数の大きい側の値
            if R != L:
                #RとLが異なればFalse
                return False
        return True

計算量はO(N)です。

結果

実装が面倒な割にとても遅いです。メモリ使用量も高いですね。

文字列に変換する方法

x を文字列に変換し反転したものと同じになるか比較するだけです。非常に簡単です。

class Solution:
    def isPalindrome(self, x: int) -> bool:
        x_str = str(x)
        if x_str == x_str[::-1]:
            return True
        return False

計算量はO(1)です。

コードはgithubにも保管しています。