◀️

LeetCode「7. Reverse Integer」

2023/07/02に公開

Python

初心者

tech

はじめに

タイトルの【Python】の代わりに、タグで「Python」つけるだけでいいではないかに気付きました。キョです。
今回はLeetCodeの「7. Reverse Integer」解いていきたいと思います。

7. Reverse Integer

問題のURLは以下になります。

内容は下記になります。

与えられた32ビット符号付き整数xについて、その桁を逆にした値を返します。xを逆にすると、値が32ビット整数の範囲[-2^31, 2^31 - 1]を超える場合は、0を返します。
環境が64ビット整数（符号付きまたは符号なし）を保存することを許可していないと仮定します。

例：

Example 1:
Input: x = 123
Output: 321

Example 2:
Input: x = -123
Output: -321

Example 3:
Input: x = 120
Output: 21

問題は難しくないと思いますが、
結果の範囲の制限があることに注意する必要がありますね。
そして、Pythonで数値計算の方法で解く時、
気をつけないといけない部分がありましたので、
この後の解決方法に記載しました。

解決方法

1.文字列に変換する方法

一番簡単な方法は文字列に変換する方法だと思います。
以下の操作を行います。

入力した数値を文字列に変換
変換後の文字列を逆転
逆転した文字列を数値に変換
入力がマイナスの場合は、マイナスにする
数値が制限範囲を超えているか判断

コードは以下になります。

def reverse1(x: int) -> int:
    str_x: str = str(x)
    flag: bool = x >= 0
    ret: int = int(str_x[::-1]) if flag else -int(str_x[:0:-1])
    return ret if (ret < (2**31 - 1)) and (ret > -(2**31)) else 0

2.数値計算の方法

文字列変換以外、数値計算をする方法もあります。
数値計算の場合は以下の操作を行います。

入力数値の絶対値をabs_x計算
abs_xを10で割った剰余を計算
abs_xを10で割った結果の整数部を再度abs_xに設定
計算結果(初回は0)を1桁増やして、abs_xを10で割った剰余を足す
計算結果が制限範囲超えているか判断
制限範囲内の場合はabs_xが0になるまで、操作２から繰り返す
繰り返し操作が完了後、入力数値と同じ符号にして返す

コードは以下になります。

def reverse2(x: int) -> int:
    ret: int = 0
    flag: bool = x >= 0
    abs_x: int = abs(x)
    while(abs_x > 0):
        l: int = abs_x % 10
        abs_x = int(abs_x / 10)
        ret = ret * 10 + l
        if (ret < -(2**31)) or (ret > ((2**31) - 1)): return 0
    return ret if flag else -ret

この方法を見ると、
入力数値の絶対値で計算しない場合、
余剰計算後の、l自体が符号持っていて、
最後の符号判断もいらないじゃないかと、
なんか違和感があるかもしれないですね。

実は私も最初、そう考えて実装してみましたが、
入力数値がマイナスになる時、正しい結果が得ることができませんでした。

調べてみた結果、
pythonの除算は以下の仕様になります。

整数の除算とも呼ばれます。結果の型は整数型とは限りませんが、結果の値は整数です。結果は常に負の無限大の方向に丸められます
https://docs.python.org/ja/3/library/stdtypes.html#numeric-types-int-float-complex

そして、余剰は以下の仕様になっています。

剰余演算子は常に第二引数と同じ符号 (またはゼロ) の結果になります; 剰余演算の結果の絶対値は、常に第二引数の絶対値よりも小さくなります。
切り捨て除算演算と剰余演算は、恒等式: x == (x//y)*y + (x%y) の関係にあります。
https://docs.python.org/ja/3/reference/expressions.html#binary-arithmetic-operations

なので、「-123」を例とした場合は、
10と除算する結果は、マイナスの無限大の方向に丸めますので、
以下のように「-13」になります。

「-123//10 = -13」

そして、余剰は「恒等式: x == (x//y)*y + (x%y) 」を満足しなければならないので、
計算結果が以下のように「7」になります。

-123%10 = 7

他の言語、例えばC言語では、「-123%10 = -3」になりますので、
そのような言語の経験者からはびっくりするかもしれないですが、
この仕様になります。
なので、一度絶対値を計算して、絶対値を利用して、計算するようにしました。

最後に

実は、この問題を共有したかったのは、
このpythonの余剰計算の仕様について共有したい気持ちが多かったでした。
もし、他の言語の経験者がpythonを利用して、何かを実装するとき、
このような仕様を分からず、前利用した言語と同じ計算結果になると思い込んで、
実装すると、気付きにくいバグを埋め込んでしまうと思いますね。

それでは、みなさん良い開発ライフをお送りください！