LeetCodeブラシ問題の旅【簡単編】——7.整数反転

4472 ワード
java lettecode
タイトル
32ビットのシンボル付き整数を与えます.この整数の各ビットの数字を反転する必要があります.
Given a 32-bit signed integer, reverse digits of an integer.
例 1:
入力:123
出力:321
例2:
入力:-123
出力:-321
例3:
入力:120
出力:21
個人的な考え方.
まず、中国語のテーマは誤解を引き起こし、32ビットには記号の整数があり、10進数の32ビットと理解しやすい.英語のタイトルから見ると、32ビットとはバイナリの32ビット、すなわちintタイプを指す.
シナリオ1:
現在の観察から、入力int数字を文字列に変換して直接逆出力することができ、以下のいくつかの特例を考慮する必要がある.
  • 負数:負数の記号には特殊な処理が必要
  • 末尾が0の場合:末尾が0のデジタル逆順出力の場合は先頭で出力不要(Javaが持つ関数を使う点は考慮しなくてもよい)
    • .
  • 特に注意が必要なのは、境界を反転する問題です.15342436469と入力し、反転後9646324351と入力するとintの値範囲[-2114748648,2147483647]を超え、Javaは異常を放出します.この異常をキャプチャし、異常がある場合は0に戻せばいいのです.

    • 実装コードは次のとおりです.
    class Solution {
    public int reverse(int x) {
        String xstr = String.valueOf(x);
        String nstr = new String();
        for (int i = xstr.length(); i > 0; i--){
            if("-".charAt(0)==xstr.charAt(i-1)){
                nstr = xstr.charAt(i-1) + nstr;
            } else{
                nstr = nstr + xstr.charAt(i-1);
            }
        }
        int result = 0;
        try{
            result = Integer.parseInt(nstr);
        } catch (Exception e){

        }
        return result;
    }
}

    実行結果:
    実行時間:19 ms、すべてのJavaコミットで5.52%のユーザーを破った
    メモリ消費量:38.3 MB、すべてのJavaコミットで5.33%のユーザーを破った
    現在のところ、この方法は比較的簡単だと考えられていますが、実現するにはコードが多く、実際には速度が遅く、メモリの占有量も多く、ここに置いて、レンガを投げて玉を引く役割があることを望んでいます.
    シナリオ2:
    前に投機をしようとするのは良い案ではないようだが、もう一つの案は、余剰を取ることで、各ビットの値を取り出し、後で反転した数字に組み合わせることだ.詳細は、ディスカッションエリアのこの解釈はを参照してください.画像はよく説明されています.次のコードを簡単に書くことができます.
    class Solution {
    public int reverse(int x) {
        int result = 0;
        while(x != 0){
            result = result * 10 + x % 10;
            x = x / 10;
        }
        return result;
    }
}

    実はこのテーマの小さな難点はどのように境界を制御するかです.まず、Javaでintの最大最小値をInteger.MAX_に格納することを復習します.VALUEとInteger.MIN_VALUEで;次に、resultを計算する過程でresult値が境界を越えた場合、異常な放出はありませんので、計算前に境界をチェックする必要があります.最大値が$maxValue$、最小値が$minValue$、計算前resultの値が$r$、xの末尾が$xTail$と記載されている場合、$r*10+xTail$r*10+xTail>minValue$が続きます:$r<(maxValue-xTail)/10$$r>(minValue-xTail)/10$右側を取り外すと、$rminValue/10-xTail/10$があればOKではないでしょうか.
    class Solution {
    public int reverse(int x) {
        int result = 0;
        while(x!=0){
            if(result > (Integer.MAX_VALUE-x%10)/10)
                return 0;
            if(result < (Integer.MIN_VALUE-x%10)/10)
                return 0;
            result = result * 10 + x % 10;
            x = x / 10;
        }
        return result;
    }
}

    それでもwrong answerになります.ここで注目すべきは、xが負数である場合、whileサイクルの最初の条件計算結果がオーバーフローすることである.xが正数である場合、第2の条件計算結果はオーバーフローする.したがって、値に関係なく0が返され、変更後:
    class Solution {
    public int reverse(int x) {
        int result = 0;
        while(x!=0){
            if(x > 0 && result > (Integer.MAX_VALUE-x%10)/10)
                return 0;
            if(x < 0 && result < (Integer.MIN_VALUE-x%10)/10)
                return 0;
            result = result * 10 + x % 10;
            x = x / 10;
        }
        return result;
    }
}

    実行結果:
    実行時間:1 ms、すべてのJavaコミットで100.00%のユーザーを破った
    メモリ消費量:36.8 MB、すべてのJavaコミットで5.33%のユーザーを破った
    公式解法
    詳細はリンク
    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;
    }
}

    異なる点はオーバーフロー境界の制御であり、私たちの前の記法に従って、$r*10+xTail$r*10+xTail>minValue$では、$rgeq maxValue/10$$rleq minValue/10$$rgeq maxValue/10$、私たちは:$r=maxValue/10$、もし$xTail>7$、計算結果がオーバーフローします.$r>maxValue/10$の場合、計算結果がオーバーフローします.同様に$rleq minValue/10$について、$r=minValue/10$の場合、$xTail<-8$の場合、計算結果はオーバーフローします.$r
    Linuxでよく使われる環境変数の変更方法
    Apache common execパッケージの対応する使用概要