leetcode 7反転整数(reverse-integer)

タイトルの説明
32ビットの符号付き整数を指定し、整数の数値を反転します.
例 1:

  : 123
  : 321

 例2:

  : -123
  : -321

例3:

  : 120
  : 21

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

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

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

 
しかし、この方法は危険です. \text{temp} =\text{rev}\cdot 10 +\text{pop}temp=rev⋅10+pop オーバーフローの原因となります.
幸いなことに、この文がオーバーフローを引き起こすかどうかを事前にチェックするのは簡単です.
説明を容易にするために \text{rev}rev 正数です.

 temp =\text{rev}\cdot 10 +\text{pop}temp=rev⋅10+pop 溢れ出すならきっと \text{rev}\geq\frac{INTMAX}{10}rev≥10INTMAX​.

 \text{rev}>frac{INTMAX}{10}rev>10 INTMAX、では temp =\text{rev}\cdot 10 +\text{pop}temp=rev⋅10+pop きっと溢れ出す.

 \text{rev}=frac{INTMAX}{10}rev=10 INTMAXであれば、 \text{pop} > 7pop>7,temp =\text{rev}\cdot 10 +\text{pop}temp=rev⋅10+pop 溢れ出す.

当 \text{rev}rev 負の場合、同様の論理を適用できます.
JAvaコード:

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;
    }
}

 c++コード:

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

 
複雑度分析
 
 
 

時間複雑度:O(log(x))O(log(x)),xx の中には \log_{10}(x)log10​(x) ビット数.

空間複雑度:O(1)O(1).

方法2:
 新しい数resを定義し、入力数字の最後のaを絶えず取得し、新しい数resを使用する.×10 aを加えて反転した数temp

class Solution {
    public int reverse(int x) {
        int res = 0;//       
        while(x != 0){
            int temp = res * 10 + x % 10;//               10           
            x = x / 10;//           
            if(temp/10 != res){
                res = 0;
                break;
            }
            res = temp;
        }
        return res;
    }
}