【LeetCode】7. Reverse Integer (Easy)
【最初に】
LeetCode 2個目に挑戦です
【問題】
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になっちゃうんですよね
もうめちゃくちゃだけど、マイナスかどうか最初に判定してやれば一応単純ケースでは動く。
あぁ、ひどいコード。オーバーフローにも対応できていないし、入力が0の場合にも答えが違う。
【解答を見る】
ここで文字列に置き換えずに数値として扱わないとオーバーフロー判定が面倒で、全然筋が違いそうな気がしてくる。ヒントを見ようと思ったけど、みんなスラスラ解けるからなのかこの問題にヒントはない。仕方ないので解答をチラ見する。そうか、10で割っていって余りをとれば1桁ずつ取れるじゃないの
めっちゃ簡単でした。10で割り続けるとintだといつか0になるのでwhile文を抜ける。
オーバーフローチェックを入れるとこんな感じかな。やっとできた。
時間計算量は O(log(x))だそう。計算量の求め方はこちらがわかりやすかったです
Oの中身はこういうルールで表記するらしい。
- 最高次数の項以外は落とす:
- 係数を無視する3n^2 -> n^2
例えば、上記のコードのループ回数は、
n=1のとき1回
n=10のとき2回
n=100のとき3回
つまり
n=10^kのときk+1回、つまり 回となり、
底数と減算は無視できるので、計算量はO(log(x))となるんじゃないかと思う。
【最後に】
新卒の頃とかにもっと基礎を勉強しとけば良かったなあ