概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。
と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。
ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
Python3で解いています。
前回
ゼロから始めるLeetCode Day60「1481. Least Number of Unique Integers after K Removals」
今はTop 100 Liked QuestionsのMediumを優先的に解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。
Twitterやってます。
問題
難易度はEasy。
32ビット符号付き整数xが与えられたとき、整数の逆数を計算するアルゴリズムを設計してください、という問題です。
Input: 123
Output: 321
Input: -123
Output: -321
Input: 120
Output: 21
解法
Pythonの場合はスライスとabsを使えば要素の指定と絶対値の管理ができるので比較的解きやすいのではないかと思います。
他の言語については知りませんが、スタックを使って解くのが一般的なのかもしれませんね。
今回は32bit整数という前提があるため、処理に入る前に別の桁を追加してもオーバーフローしないかを事前に確認しておく方が良いでしょう。
Pythonではint型に最大値がないのでメモリの有る限りいくらでも計算できます。
なので以下のように自分で設定しておく必要があります。
max_32 = 2**31 - 1
最初にこの値よりxが大きかった場合は無条件で0を返すときちんと場合分けできていると思います。
そして、この後の分岐ですが、正の値ならば後ろから要素を取ってあげて、負の値ならば絶対値の逆から要素を取ってあげて代入する前に-を付けてあげます。
Pythonでは負の値ならば代入する要素の先頭に-を付けてあげると反転し直した後にも-がついた状態になります。
反転させたものを内包表記で書けば良くない？と思う方がいらっしゃるかもしれませんが、これだけで処理を終わらせてしまってはオーバーフローする可能性がまだ残っている可能性があります。
なので、最後の分岐に仮にオーバーフローしそうなら0を返し、それ以外の場合にのみ反転した値を返せば完成です。
これらの一連の流れをまとめたものが以下になります。
class Solution:
def reverse(self, x: int) -> int:
max_32 = 2**31 - 1
if abs(x) > max_32:
return 0
if x < 0:
reverse_int = -int(str(abs(x))[::-1])
else:
reverse_int = int(str(x)[::-1])
if abs(reverse_int) > max_32:
return 0
else:
return reverse_int
# Runtime: 28 ms, faster than 86.13% of Python3 online submissions for Reverse Integer.
# Memory Usage: 14 MB, less than 9.77% of Python3 online submissions for Reverse Integer.
そういえば新しくブログを始めました。
Qiitaでも発信は続けて行く予定ですが、まったりとした内容で書ける技術・ガジェットブログみたいな感じで書く予定なので興味ある方はプロフィールからどうぞ。
今回はここまで。お疲れ様でした。