每日一道 LeetCode (2)：整數(shù)反轉(zhuǎn)

題目：整數(shù)反轉(zhuǎn)

題目來(lái)源：https://leetcode-cn.com/problems/reverse-integer

給出一個(gè) 32 位的有符號(hào)整數(shù)，你需要將這個(gè)整數(shù)中每位上的數(shù)字進(jìn)行反轉(zhuǎn)。

示例?1:

輸入: 123
輸出: 321

示例 2:

輸入: -123
輸出: -321

示例 3:

輸入: 120
輸出: 21

注意:

假設(shè)我們的環(huán)境只能存儲(chǔ)得下 32 位的有符號(hào)整數(shù)，則其數(shù)值范圍為?[?2^31, ?2^31 ? 1]。請(qǐng)根據(jù)這個(gè)假設(shè)，如果反轉(zhuǎn)后整數(shù)溢出那么就返回 0。

解題思路

題目中對(duì)數(shù)字反轉(zhuǎn)的結(jié)果有最大最小限制，這個(gè)限制實(shí)際上在 Java 中也是 int 類型的大小限制，把 [?2^31, ?2^31 ? 1] 這個(gè)公式計(jì)算一下，結(jié)果就是 [-2147483648, 2147483647] 。

接下來(lái)的就只剩下一個(gè)問(wèn)題了，如何把一個(gè)整數(shù)進(jìn)行反轉(zhuǎn)。

我這里提供一個(gè)思路，我們對(duì)原數(shù)字除以 10 以后進(jìn)行取模運(yùn)算（取余數(shù)）:

大體思路就是上面這樣，然后注意邊緣值判斷，代碼基本上就按照這個(gè)思路來(lái)：

public int reverse(int x) {
    int res = 0;
    while (x != 0) {
        // 先獲取末尾數(shù)字
        int tmp = x % 10;

        if (res < -214748364 || (res == -214748364 && tmp < -8)) {
            return 0;
        }

        if (res > 214748364 || (res == 214748364 && tmp > 7)) {
            return 0;
        }

        res = res * 10 + tmp;
        x /= 10;
    }
    return res;
}

這種邊界判斷方式稍顯笨重，我看了看別人的答案，看到一種溢出的判斷思路，感覺(jué)不錯(cuò)分享下：

public int reverse_1(int x) {
    int res = 0;
    while (x != 0) {

        if (res > 214748364 || res < -214748364) {
            return 0;
        }

        res = res * 10 + x % 10;
        x /= 10;
    }
    return res;
}

這個(gè)結(jié)果提交 LeetCode 以后，直接看到 LeetCode 說(shuō)執(zhí)行耗時(shí)超過(guò) 100% 的用戶。

簡(jiǎn)直意外的驚喜，這里的判斷極限值的含義如下：1463847412

極限最大值是 2147483648 ，除以 10 以后是 214748364 ，這里當(dāng) res 是 214748364 時(shí)，輸入的 x 只能是 1463847412 ，因?yàn)?2463847412 、 3463847412 這些數(shù)字本身已經(jīng) int 溢出了。

思路非常巧妙，利用了 int 本身的溢出范圍，限制了輸入數(shù)據(jù)的大小，減少了需要判斷的可能性。