Palindrome Number
数字は、1221のように、左から右に読んでも右から左に読んでも同じ桁になる場合、回文です。整数xが与えられたとき、回文であればtrueを返し、そうでなければfalseを返してください。負の数は、マイナス記号に反対側の対応する記号がないため、回文にはなりません。
関数
- xinteger
- 確認する整数（負の数の場合もあります）
- 戻り値boolean
- xがどちらの方向から読んでも同じなら真、そうでなければ偽
制約
-231 ≤ x ≤ 231-1- すべての負の数は
falseを返します。
例
- 入力
- x = 121
- 出力
- true
- 説明
- 逆から読んでも、121は依然として121なので、答えは
trueです。
- 入力
- x = -121
- 出力
- false
- 説明
- 逆から読むと、
-121は121-になり、異なる文字列になるので、答えはfalseです。
発展問題
整数を文字列に変換せずに解けますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
負の数が回文になることは決してないので、最初に処理しましょう。
x % 10で最後の桁を取り出し、10による整数除算でその桁を取り除きます。reversed = reversed * 10 + digitを使って逆順の数を作り、その後、元の数と比較します。
解説
数値は、逆順にした数値と等しいとき、回文です。テキストとして扱う場合は、比較するだけです。テキストを使わずに逆順の数値全体を作り直すとオーバーフローする可能性があるため、数字の後半だけを逆順にして、前半と比較します。
文字列とその逆順を比較する
考え方
数値をテキストとして書き、その逆順のものと比較します。負の数に特別な処理は必要ありません。-121はマイナス記号で始まり数字で終わるため、逆順の121-と等しくなることはありません。
テキストには数字ごとに1文字あり、その数はおよそlog10(x)文字で、ここでは最大11文字です。コストは追加の文字列です。
アルゴリズム
xを文字列sに変換します。sを反転します。sが反転したものと等しいかどうかを返します。
def isPalindrome(x):
s = str(x)
# A minus sign sits only at the front, so a negative never matches its reverse.
return s == s[::-1]数値の半分を反転する
考え方
x % 10は最後の桁を取り出し、10で整数除算するとその桁が取り除かれます。xの末尾から数字を取り出して2つ目の数値halfに移すと、取り除いた数字を逆順に並べた数値が作られます。halfがxの残り以上になったら停止します。数字の半分を取り出したことになります。1221は、x = 12、half = 12となり、回文です。桁数が奇数の場合、halfには中央の桁も含まれます。12321は、x = 12、half = 123となるため、xとhalf / 10を比較します。
ループの前に、2つのケースを処理します。負の数が回文になることはありません。末尾が0の数は、先頭も0でなければなりませんが、それに当てはまるのは0だけです。このチェックがないと、10はx = 0、half = 1となり、x == half / 10が誤って成立してしまいます。halfは6桁を超えることがないため、どの整数型にも収まります。
アルゴリズム
xが負の場合、または 0 でないのに 0 で終わる場合は、falseを返します。half = 0を設定します。x > halfの間、half = half * 10 + x % 10を設定し、整数除算でxを 10 で割ります。x == half（桁数が偶数）またはx == half / 10（桁数が奇数）の場合は、trueを返します。
def isPalindrome(x):
if x < 0:
return False
original, reversed_num = x, 0
while x > 0:
reversed_num = reversed_num * 10 + x % 10
x //= 10
return original == reversed_num
落とし穴と境界ケース
- 負の数を考慮し忘れる。余りが符号を保つ言語では、
-121を反転すると-121になり、判定に合格します。-1 // 10が-1となるPythonでは、while x != 0のループが終わりません。 - 末尾が0の数を除外しない。すると、半分を反転する方法では
10が受け入れられてしまいます。0自体は回文です。 - 32ビット整数で数全体を反転する。
2147483647を反転した値は、範囲に収まりません。 - 言語が分数で除算する場合に
/を使う。JavaScriptではMath.floor(x / 10)、Pythonでは//、Rでは%/%、Dartでは~/を使います。 - ループで
xが変更された後に、反転した値全体とxを比較する。元の値をコピーしておきましょう。
よくある質問3
負の数は回文ですか？
いいえ。逆から読むと、-121は121-となり、反対側に対応する文字がないマイナス記号が残ります。したがって、すべての負の整数はfalseを返します。
なぜ数値の半分だけを逆順にするのですか？
すべての桁を反転すると、32ビット整数でオーバーフローすることがあります。2147483647を反転した値は、最大のintより大きくなります。桁の半分なら常に収まり、ループの処理も半分で済みます。
回文数の時間計算量はどれくらいですか？
どちらの方法も O(log x) 時間で実行されます。数値 x は約 log10(x) 桁で、それぞれの桁を一度ずつ処理するためです。文字列を使う方法ではテキスト用に O(log x) の追加領域を使用し、半分を反転する方法では O(1) を使用します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def isPalindrome(x):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
x = 121
期待される出力
true