LeetCode刷题第二题，整数反转

题目描述

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。例如：
输入：321，输出123
输入：-321，输出：-123
输入：120，输出：21
注意事项：
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

解题思路1：字符串切片实现逆序

1.将原始数组由int转换成str字符串的形式，方便将"-“号提出与添加；
2.利用Python中的字符串切片方法，逆序输出新的字符串，并去除掉字符串开头可能存在的"0"和结尾可能出现的”-"两个字符；
3.把新生成的逆序字符串转换成int形式；
4.最后判断逆序数组的大小范围。
代码如下所示：

class Solution:
    def reverse(self, x: int) -> int:
        if x == 0:
            return 0
        str_x = str(x) # 把数组x转换成字符串的形式
        x = ''
        if str_x[0] == '-': # 数组字符串的表示形式方便"-"的提取与插入
            x += '-'
        x += str_x[len(str_x)-1::-1].lstrip("0").rstrip("-") # .lstrip()表示删除最左侧的指定字符，.rstrip()表示删除最右侧的指定字符
        x = int(x) # 把字符串形式的逆序数组转换成int整数形式
        if -2**31<x<2**31-1: # 判断x的大小范围
            return x
        return 0
""" len(str_x)-1::-1,为字符串切片的表示方法，表示从最后一个字符到第一个字符的逆序表示， A:B:x,A为起始位置，B为结束位置，x为步长，B可以省略，写成A::x的形式。 """ 

执行通过，时间为48ms。
时间复杂度O(n)。
空间复杂度为O(n)。

解题思路2：优化解

思路如下：
我们可以一次构建反转整数的一位数字。在这样做的时候，我们可以预先检查向原整数附加另一位数字是否会导致溢出。
反转整数的方法可以与反转字符串进行类比。
我们想重复“弹出” x 的最后一位数字，并将它“推入”到 res 的后面。最后，res 将与 x 相反。
时间复杂度：O(log(x))，x中大约有log10(x) 位数字。
空间复杂度：O(n)
代码如下：

class Solution:
    def reverse(self, x: int) -> int:
        y, res = abs(x), 0
        # 则其数值范围为 [−2^31, 2^31 − 1]
        boundry = (1<<31) -1 if x>0 else 1<<31
        while y != 0:
            res = res*10 +y%10
            if res > boundry :
                return 0
            y //=10
        return res if x >0 else -res

执行通过，运行时间为42ms。

解题思路3：运用堆栈解决

方法三来自LeetCode题目讨论区，觉得思路值得借鉴，以供大家参考。

class Solution:
    def reverse(self, x: int) -> int:
        x_list = list(str(x))
        res_stack = []
        is_minus = False  # 用于处理负数
        
        while x_list:
            v = x_list.pop()
            if v == '-':
                is_minus = True
                continue
            res_stack.append(v)
        res = int(''.join(res_stack))
        
        if is_minus:
            res *= -1
        
        # 边界条件
        v_max = 0xffffffff/2
        if res > (v_max -1) or res < (v_max*(-1)):
            res = 0
            
        return res