【leetCode】整數反轉
題目
給出一個(gè) 32 位的有符號整數，你需要將這個(gè)整數中每位上的數字進(jìn)行反轉。
示例 1:
輸入: 123
輸出: 321
示例 2:
輸入: -123
輸出: -321
示例 3:
輸入: 120
輸出: 21
注意:
假設我們的環(huán)境只能存儲得下 32 位的有符號整數，則其數值范圍為 [?231, 231 ? 1]。請根據這個(gè)假設，如果反轉后整數溢出那么就返回 0。
鏈接：https://leetcode-cn.com/problems/reverse-integer
題目解答
方法：彈出和推入數字 & 溢出前進(jìn)行檢查
思路
我們可以一次構建反轉整數的一位數字。在這樣做的時(shí)候，我們可以預先檢查向原整數附加另一位數字是否會(huì )導致溢出。
算法
反轉整數的方法可以與反轉字符串進(jìn)行類(lèi)比。
我們想重復“彈出” x 的最后一位數字，并將它“推入”到 \text{rev}的后面。最后， \text{rev} 將與 x 相反。
要在沒(méi)有輔助堆棧 / 數組的幫助下 “彈出” 和 “推入” 數字，我們可以使用數學(xué)方法。
//pop operation:
pop = x % 10;
x /= 10;//push operation:
temp = rev * 10 + pop;
rev = temp;
但是，這種方法很危險，因為當 temp=rev?10+pop 時(shí)會(huì )導致溢出。
幸運的是，事先檢查這個(gè)語(yǔ)句是否會(huì )導致溢出很容易。
為了便于解釋?zhuān)覀兗僭O \text{rev} 是正數。
如果 temp=rev?10+pop 導致溢出，那么一定有 \text{rev} \geq \frac{INTMAX}{10}。
如果 \text{rev} > \frac{INTMAX}{10}
，那么 temp=rev?10+pop 一定會(huì )溢出。
如果 \text{rev} == \frac{INTMAX}{10} ，那么只要 \text{pop} > 7，temp=rev?10+pop 就會(huì )溢出。
當 \text{rev} 為負時(shí)可以應用類(lèi)似的邏輯。
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;
}
復雜度分析
時(shí)間復雜度：O(\log(x))，x 中大約有 \log_{10}(x) 位數字。
空間復雜度：O(1)。
評論
