小編溫馨提示,今天是我們堅(jiān)持的第7天! 今天休息日,降低了些難度.讓大家輕松的放假也能學(xué)習(xí)哦

一.題目

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

• 例如:

輸入: 123
輸出: 321

輸入: 120
輸出: 21

輸入: -123
輸出: -321

• 注意
  

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

二.解決方案

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

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

3.算法
反轉(zhuǎn)整數(shù)可以和反轉(zhuǎn)字符串一起類比實(shí)現(xiàn).
在沒有輔助的堆棧/數(shù)組的幫助下,'彈出'和'推入'數(shù)字,可以嘗試有用數(shù)學(xué)的方式.

但是,當(dāng)因?yàn)楫?dāng) temp = rev*10+pop時(shí),有可能會(huì)造成溢出.

4.解決溢出

• 假設(shè)rev,為正數(shù)

• 如果temp = rev*10+pop,導(dǎo)致溢出.那么一定rev >= INTMAX/10;

• 如果rev > INTMAX / 10;那么temp = rev*10+pop 一定會(huì)溢出

• 如果rev == INTMAX / 10,那么只要pop > 7 ,temp = rev*10+pop 就會(huì)溢出

三.代碼實(shí)現(xiàn)
C++ Code

四.復(fù)雜度

• 時(shí)間復(fù)雜度:O(log(x))

• 空間復(fù)雜度:O(1)

小編OS:

如有疑問,留言即可.胖C會(huì)利用空余時(shí)間給大家做一個(gè)簡(jiǎn)單解答的.
持續(xù)更新關(guān)注公眾號(hào)!