算法學習-整數反轉

題目和需求

給你一個 32 位的有符号整數 x ，傳回将 x 中的數字部分反轉後的結果。

如果反轉後整數超過 32 位的有符号整數的範圍 [−231,  231 − 1] ，就傳回 0。

正常解法

使用字元串回轉方法(一般開發中的思路)

public static int reverse1(int x) {
        if (x == 0) {
            return 0;
        } else {
            String temp = String.valueOf(x);
            StringBuilder sb = new StringBuilder();
            int length = temp.length();
            if (x > 0) {
                for (int i = 0; i < length; i++) {
                    sb.append(temp.charAt(length - i - 1));
                }
                return Integer.valueOf(sb.toString());
            } else {
                for (int i = 0; i < length - 1; i++) {
                    sb.append(temp.charAt(length - i - 1));
                }
                return -Integer.valueOf(sb.toString());
            }
        }
    }      

這個沒有特殊技巧，就是一般實際工作中常見的思路，提出需求你，按需求思路解決需求。

改進算法

public int reverse(int x) {
        long n = 0;
        while(x != 0) {
            n = n * 10 + x % 10;
            x = x / 10;
        }
        return (int)n==n? (int)n:0;
    }      

結題思路：

由于int反轉後，可能會超過int最大值，是以使用long存儲中間值，最後用強轉後對比值大小判斷是否有值溢出

從後往前，每次取到除以10的餘數，每次循環一次，将上次所得值乘以10.

更多限制

public static int reverse(int x) {
        if (x == 0) {
            return 0;
        } else {
            int ret = 0;
            while (x != 0) {
                int temp = ret;
                ret = (ret * 10) + (x % 10);
                if (temp != ret / 10)
                    return 0;
                x = x / 10;
            }
            return ret;
        }
    }      

if (temp != ret / 10)一定要在加法完成後計算是否越界
有些算法喜歡直接在上一步就比較是否大于int.maxvalue和小于int.minvalue,這是錯的，因為java溢出繼續添加，并不會報錯，而是會繼續進位。