7. Reverse Integer

tianren124 發(fā)布于2019-07-30 17:00 / 1283人閱讀

摘要：題目鏈接思路因為中的數(shù)字是沒有的，即取決于電腦的內(nèi)存。不過題目有額外要求，假設(shè)我們只能處理的數(shù)字區(qū)間。所以需要另外加一個判斷。另外，內(nèi)置的函數(shù)可以把轉(zhuǎn)換成數(shù)字。數(shù)字要注意區(qū)分正負(fù)。負(fù)數(shù)反轉(zhuǎn)還是負(fù)數(shù)。

題目鏈接：Reverse Integer

思路：
因為Python中的數(shù)字是沒有overflow的，即limit取決于電腦的內(nèi)存。不過題目有額外要求，假設(shè)我們只能處理
32-bit signed 的數(shù)字區(qū)間。所以需要另外加一個判斷。另外，Python內(nèi)置的int()函數(shù)可以把 "001" 轉(zhuǎn)換成數(shù)字 1。

數(shù)字要注意區(qū)分正負(fù)。負(fù)數(shù)反轉(zhuǎn)還是負(fù)數(shù)。對于Python來說，有兩種解法：

可以把數(shù)字轉(zhuǎn)換成字符串反轉(zhuǎn)然后轉(zhuǎn)換回數(shù)字

可以把反轉(zhuǎn)的數(shù)字乘以10加上x % 10，x每次除以10直到0為止

算法復(fù)雜度：
Pythonic:

時間：O(x)
空間：O(n) where n is the length of x

一般方法：

時間：O(logx) 
空間：O(n) where n is the length of x

代碼：

Pythonic Approach

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            minus_sign = str(x)[0]
            abs_x = abs(x)
            res = minus_sign + str(abs_x)[::-1]
            if int(res) > 2**31-1 or int(res) < -2**31:
                return 0
            else:
                return int(res)
        else:
            if int(str(x)[::-1]) > 2**31-1 or int(str(x)[::-1]) < -2**31:
                return 0
            else:
                return int(str(x)[::-1])

一般方法

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        sign = 1 if x > 0 else -1
        x = abs(x)
        t = 0
        while x:
            t = t*10 + x % 10
            x  //= 10
        t = t * sign
        if t > 2**31-1 or t < -2**31:
            return 0
        else:
            return t