LeetCode 題解 | 7. 反轉整數

08-15

來自專欄領扣（LeetCode）4 人贊了文章

題目描述：

給定一個 32 位有符號整數，將整數中的數字進行反轉。

示例 1:

輸入: 123輸出: 321

示例 2:

輸入: -123輸出: -321

示例 3:

輸入: 120輸出: 21

注意:

假設我們的環境只能存儲 32 位有符號整數，其數值範圍是 $[?2^{31}, 2^{31} ? 1]$ 。根據這個假設，如果反轉後的整數溢出，則返回 0。

反轉整數 - LeetCode (中國)?

leetcode-cn.com

彈出和推入數字 & 溢出前進行檢查：

思路

我們可以一次構建反轉整數的一位數字。在這樣做的時候，我們可以預先檢查向原整數附加另一位數字是否會導致溢出。

演算法

反轉整數的方法可以與反轉字元串進行類比。

我們想重複「彈出」 $x$ 的最後一位數字，並將它「推入」到 rev 的後面。最後， $rev$ 將與 $x$ 相反。

要在沒有輔助堆棧 / 數組的幫助下「彈出」和「推入」數字，我們可以使用數學方法。

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

但是，這種方法很危險，因為當 $temp=rev cdot 10 + pop$ 時會導致溢出。

幸運的是，事先檢查這個語句是否會導致溢出很容易。

為了便於解釋，我們假設 $rev$ 是正數。

如果 $temp= rev?10+pop$ 導致溢出，那麼一定有 $revgeqfrac{INTMAX}{10}$ 。
如果 $rev>frac{INTMAX}{10}$ ?，那麼 $temp=rev?10+pop$ 一定會溢出。
如果 $rev ==frac{INTMAX}{10}$ ???，那麼只要 $pop>7$ ， $temp=rev?10+pop$ 就會溢出。

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

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

複雜度分析

時間複雜度： $O(log(x))$ ， $x$ 中大約有 $log_{10}(x)$ 位數字。
空間複雜度： $O(1)$ 。