LeetCode: Reverse Integer

問題

Given a 32-bit signed integer, reverse digits of an integer.

解答

どうしようか迷ったのですが、入力値をStringにして反転して出力するのが一番楽そうだなと思ってそれで実装することにしました。 反転した値がオーバーフローする場合は0を返す仕様だったので、 x == Integer.MIN_VALUE の確認を入れたり、 Integer.parseIntNumberFormatExceptionが発生した時は0を返すようにしました。(後者だけで良かったかも?)

class Solution {
    public int reverse(int x) {
        try {
          if (x == Integer.MIN_VALUE) {
            return 0;
          }
          StringBuffer sb = new StringBuffer(String.valueOf(Math.abs(x)));
          int ans = Integer.parseInt(sb.reverse().toString());
          if (x < 0) {
            return -ans;
          } else {
            return ans;
          }
        } catch (NumberFormatException e) {
          return 0;
        }
    }
}

時間計算量:O(log n)、メモリ計算量:O(1)

(時間計算量について:SutringBufferのreverse()が文字列の長さnに対してO(n)なので、今回の問題の入力値nに対してはO(log10 n)のはず。)

他の人の解答も見てみましょう。 多くの人の解答はこんな感じのようです。

class Solution {
    public static int reverse(int x) {
        int counter = digitsCount(x);
        int sign = x >= 0 ? 1 : -1;

        long value = 0;
        x = Math.abs(x);
        while (x > 0 && value <= Integer.MAX_VALUE) {
            value += x % 10 * Math.pow(10, counter - 1);
            counter--;
            x /= 10;
        }
        if (value <= Integer.MAX_VALUE) {
            return (int) (value * sign);   
        } else {
            return 0;
        }
    }

    private static int digitsCount(int x) {
        x = Math.abs(x);
        int counter = 0;
        while (x > 0) {
            x /= 10;
            counter++;
        }
        return counter;
    }
}

時間計算量:O(log n) 、メモリ計算量:O(1)

普通に1桁ずつ逆にしているという感じですね。