割り算と余りで整数が回文かを確かめる - LeetCode 9

整数を前から読んでも後ろから読んでも同じ数かを判定します。文字列に直さず、10 で割った余りで下の桁から取り出し、後ろ半分だけを逆に組み立てて比べる練習です。

海外で定番の問題リスト 4 本のうち 1 本に入っています (LeetCode Top Interview 150)

問題

整数 x を受け取ります。x を 10 進数で書いたとき、前から読んでも後ろから読んでも同じ並びになるなら真、ならないなら偽を返す関数を書いてください。

  • 負の数は回文ではないものとします。-121 を後ろから読むと 121- になり、同じ並びにならないからです
  • 0 から 9 までの 1 桁の数は、どれも回文です
  • x は -2147483648 以上 2147483647 以下です
  • 数を文字列に直さず、数のままの計算だけで判定してください

入力と出力の例

例 1

桁の数が偶数でも回文になります。

入力

x = 2552

出力

true

例 2

入力

x = 1534

出力

false

例 3

負の数は、数字の並びが左右で同じに見えても回文ではありません。

入力

x = -404

出力

false

図で見る

例 1 で、解き方がどう動くか。押すと大きく開きます。

面接での聞かれ方

面接では、最初は短く聞かれ、条件があとから足されることが多いです。

  • 「整数が回文かどうかを判定してください」
  • 文字列に直して逆にした書き方を見せると、「では、文字列に直さずに解けますか?」と続きます
  • 「負の数や、末尾が 0 の数はどうなりますか?」と、端の場合を聞かれます

文字列に直す書き方も正しく動きます。ただ、ここで見られているのは、10 で割った余りと商で桁を扱えるかどうかです。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

  1. ヒント 2

  2. ヒント 3

  3. ヒント 4答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

main.py
def is_palindrome_number(x: int) -> bool:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(is_palindrome_number(2552))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します