サンダーボルト

相手モンスターを全て破壊する。

LeetCode Study : 7. Reverse Integer

問題

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

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

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

Note:

Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [-2^{31}, 2^{31} − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

自分の解答1

public int reverse(int x) {
    if (x == 0) {
        return 0;
    }
    int processedX = x;
    boolean isNegative = x < 0;
    if (isNegative) {
        processedX = processedX * -1;
    }
    while (processedX % 10 == 0) {
        processedX /= 10;
    }
    String str = String.valueOf(processedX);
    char[] chars = str.toCharArray();
    int charsLength = chars.length;
    char[] reversedChars = new char[charsLength];
    for (int i = 0; i < charsLength; i++) {
        reversedChars[i] = chars[charsLength - 1 - i];
    }
    try {
        return Integer.parseInt((isNegative ? "-" : "") + String.valueOf(reversedChars));
    } catch (Exception e) {
        return 0;
    }
}

自分の解答2

public int reverse(int x) {
    if (x == 0 || x == Integer.MIN_VALUE) {
        return 0;
    }
    while (x % 10 == 0) {
        x /= 10;
    }
    boolean isNegative = false;
    if (x < 0) {
        isNegative = true;
        x *= -1;
    }
    String[] reversed = new String[(int) Math.floor(Math.log10(x) + 1.0)];

    int index = 0;
    while (x != 0) {
        reversed[index] = String.valueOf(x % 10);
        x = (int) Math.floor(x /= 10);
        index++;
    }
    String reversedString = (isNegative ? "-" : "") + String.join("", reversed);
    try {
        return Integer.parseInt(reversedString);
    } catch (Exception e) {
        return 0;
    }
}

コード理解

別解

public int reverse3(int x) {
    long reversed = 0;
    while (x != 0) {
        reversed = reversed * 10 + x % 10;
        if (reversed > Integer.MAX_VALUE || reversed < Integer.MIN_VALUE) {
            return 0;
        }
        x /= 10;
    }
    return (int) reversed;
}

Time : O( \log x ) / Space : O(1)

(Time is roughly  \log_{10} x digits in  x.)

愚直にやっているので自分の1は実行速度は速めだが汚い。2もシンプルにしようとしたけど結局汚い。

別解ポイントは x % 10で1の位の数が取得でき、さらにreverse = reverse * 10 + reminderでうまくずらして数を増やせること。 ただし、負の数の剰余は言語によって仕様が違うらしい。

参考: shunirr.hatenablog.jp

なので、xが負だったら一旦正にしてやった方が皆が見やすいいいコードになるかも。

また、桁数がそのまま速度に直結するのでTime complexityはO( \log x ) となる

今後のための考え方

  • popとpushは以下のようにできる
// pop
pop = x % 10;
x /= 10;

// push
rev = rev * 10 + pop;
  • 負数の剰余は言語によって仕様が違う(ので、基本的には使わない)
  • 桁数によって時間が変わるときの計算量はO( \log x )
  • intでoverflowを気にするときはlongを用いる
  • テストするときはInteger.MAX_VALUE/MIN_VALUEを忘れない