問題
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: [, − 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() / Space : O(1)
(Time is roughly digits in .)
愚直にやっているので自分の1は実行速度は速めだが汚い。2もシンプルにしようとしたけど結局汚い。
別解ポイントは
x % 10
で1の位の数が取得でき、さらにreverse = reverse * 10 + reminder
でうまくずらして数を増やせること。
ただし、負の数の剰余は言語によって仕様が違うらしい。
なので、xが負だったら一旦正にしてやった方が皆が見やすいいいコードになるかも。
また、桁数がそのまま速度に直結するのでTime complexityはO() となる
今後のための考え方
- popとpushは以下のようにできる
// pop pop = x % 10; x /= 10; // push rev = rev * 10 + pop;