【スナップアルゴリズム】7-整数反転

タイトル
32ビットのシンボル付き整数を与えます.この整数の各ビットの数字を反転する必要があります.
例1:

  : 123
  : 321

例2:

  : -123
  : -321

例3:

  : 120
  : 21

注意:
我々の環境では32ビット以下の符号付き整数しか記憶できないと仮定すると,その数値範囲は[−231,231−1]である.この仮定に基づいて、反転後に整数がオーバーフローした場合は0を返します.
問題解
ソリューション
方法:数値&オーバーフロー前のチェックをポップアップおよびプッシュ
構想
反転整数の1桁の数値を一度に構築することができます.このようにすると,元の整数に別の数字を付加してオーバーフローを招くかどうかを事前にチェックすることができる.
アルゴリズム#アルゴリズム#
整数を反転する方法は、反転文字列とクラス比できます.
「ポップアップ」xの最後の数字を繰り返し、revの後ろに「プッシュ」したい.最後にrevはxとは逆になります.
補助スタック/配列の助けなしに「ポップアップ」と「プッシュ」の数字を使用するには、数学的な方法を使用します.

//pop operation:
pop = x % 10;
x /= 10;

//push operation:
temp = rev * 10 + pop;
rev = temp;

しかし、temp=rev⋅10+popの場合、オーバーフローを引き起こすため、この方法は危険である.
幸いなことに、この文がオーバーフローを引き起こすかどうかを事前にチェックするのは簡単です.
説明を容易にするためにrevを正数と仮定した.

temp=rev⋅10+popがオーバーフローを引き起こす場合、rev≧IN T M A X 10text{rev}geqfrac{INTMAX}{10}rev≧10 INTMAXがあるに違いない.

$text{rev}>frac{INTMAX}{10}$の場合、temp=rev⋅10+popは必ずオーバーフローします.

rev==INT MA X 10text{rev}==frac{INTMAX}{10}rev=10 INTMAXの場合、pop>7であればtemp=rev⋅10+popが溢れ出す.

revが負の場合、同様の論理を適用することができる.

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

複雑度分析

時間複雑度:O*(log(*x))、xには約log⁡10(x)log_{10}(x)log 10(x)ビット数.

空間複雑度:O(1).

感想
オーバーフロー判定がちょっと面白い