題目

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

示例 1:

輸入: 123
輸出: 321

示例 2:

輸入: -123
輸出: -321

示例 3:

輸入: 120
輸出: 21

注意:

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

鏈接：https://leetcode-cn.com/problems/reverse-integer

題目解答

方法：彈出和推入數(shù)字 & 溢出前進(jìn)行檢查
思路

我們可以一次構(gòu)建反轉(zhuǎn)整數(shù)的一位數(shù)字。在這樣做的時候，我們可以預(yù)先檢查向原整數(shù)附加另一位數(shù)字是否會導(dǎo)致溢出。

算法

反轉(zhuǎn)整數(shù)的方法可以與反轉(zhuǎn)字符串進(jìn)行類比。

我們想重復(fù)“彈出” 的最后一位數(shù)字，并將它“推入”到的后面。最后， 將與 相反。

要在沒有輔助堆棧 / 數(shù)組的幫助下 “彈出” 和 “推入” 數(shù)字，我們可以使用數(shù)學(xué)方法。

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

但是，這種方法很危險，因為當(dāng) 時會導(dǎo)致溢出。

幸運(yùn)的是，事先檢查這個語句是否會導(dǎo)致溢出很容易。

為了便于解釋，我們假設(shè)是正數(shù)。

如果 導(dǎo)致溢出，那么一定有 。
如果

，那么 一定會溢出。
如果 ，那么只要 ， 就會溢出。
當(dāng) 為負(fù)時可以應(yīng)用類似的邏輯。

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

復(fù)雜度分析

時間復(fù)雜度：， 中大約有 位數(shù)字。

空間復(fù)雜度：。

標(biāo) 題：《【leetCode】整數(shù)反轉(zhuǎn)》
作 者：zeekling
提 示：轉(zhuǎn)載請注明文章轉(zhuǎn)載自個人博客：小令童鞋