NinaLabo

個人ゲーム開発者の技術メモ

【LeetCode】7. Reverse Integer (Easy)

【最初に】

LeetCode 2個目に挑戦です

leetcode.com

 

 

 

【問題】

https://leetcode.com/problems/reverse-integer/

32bit signed integer(−231 〜 231 − 1) の桁を逆順にせよ。 逆順の数値がオーバーフローした場合は0を返すものとする

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

 

 

【とりあえず】

パッと思いつくのは、文字列にして1つずつ逆順にして最後に数値に変換。頑張って書いてみたけど、これだと-123の時に-321ではなく321になっちゃうんですよね

f:id:ninagreen:20191107011119p:plain

もうめちゃくちゃだけど、マイナスかどうか最初に判定してやれば一応単純ケースでは動く。

f:id:ninagreen:20191107011848p:plain

あぁ、ひどいコード。オーバーフローにも対応できていないし、入力が0の場合にも答えが違う。

 

【解答を見る】

ここで文字列に置き換えずに数値として扱わないとオーバーフロー判定が面倒で、全然筋が違いそうな気がしてくる。ヒントを見ようと思ったけど、みんなスラスラ解けるからなのかこの問題にヒントはない。仕方ないので解答をチラ見する。そうか、10で割っていって余りをとれば1桁ずつ取れるじゃないの

f:id:ninagreen:20191107013317p:plain

めっちゃ簡単でした。10で割り続けるとintだといつか0になるのでwhile文を抜ける。

 

オーバーフローチェックを入れるとこんな感じかな。やっとできた。

f:id:ninagreen:20191107014538p:plain

 

時間計算量は O(log(x))だそう。計算量の求め方はこちらがわかりやすかったです

qiita.com

 

Oの中身はこういうルールで表記するらしい。

  1. 最高次数の項以外は落とす: 3n^2+5n+100 -> 3n^2
  2. 係数を無視する3n^2 -> n^2

例えば、上記のコードのループ回数は、

n=1のとき1回

n=10のとき2回

n=100のとき3回

つまり

n=10^kのときk+1回、つまり \log_{10} n - 1 回となり、

底数と減算は無視できるので、計算量はO(log(x))となるんじゃないかと思う。

 

【最後に】

新卒の頃とかにもっと基礎を勉強しとけば良かったなあ