20180919-摘抄自7. 反轉(zhuǎn)整數(shù)
給定一個 32 位有符號整數(shù)，將整數(shù)中的數(shù)字進行反轉(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材义。
解決方案
方法：彈出和推入數(shù)字 & 溢出前進行檢查
思路
我們可以一次構(gòu)建反轉(zhuǎn)整數(shù)的一位數(shù)字。在這樣做的時候嫁赏，我們可以預先檢查向原整數(shù)附加另一位數(shù)字是否會導致溢出其掂。
算法
反轉(zhuǎn)整數(shù)的方法可以與反轉(zhuǎn)字符串進行類比。
我們想重復“彈出” x 的最后一位數(shù)字潦蝇，并將它“推入”到 rev 的后面款熬。最后，rev 將與 x 相反护蝶。
要在沒有輔助堆棧 / 數(shù)組的幫助下 “彈出” 和 “推入” 數(shù)字华烟，我們可以使用數(shù)學方法。
//pop operation:
pop = x % 10;
x /= 10;
//push operation:
temp = rev * 10 + pop;
rev = temp;
但是持灰，這種方法很危險盔夜，因為當 temp = rev * 10 + pop 時會導致溢出。
幸運的是堤魁，事先檢查這個語句是否會導致溢出很容易喂链。
為了便于解釋，我們假設(shè) rev 是正數(shù)妥泉。
如果 temp = rev * 10 + pop 導致溢出椭微，那么一定有 rev ≥ INTMAX / 10。
如果 rev > INTMAX / 10盲链，那么 temp = rev * 10 + pop 一定會溢出蝇率。
如果 rev == INTMAX / 10迟杂，那么只要 pop > 7，temp = rev * 10 + pop 就會溢出本慕。
當 rev 為負時可以應用類似的邏輯排拷。
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) 位數(shù)字锅尘。
- 空間復雜度：O(1)监氢。
