7. 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：
输入：x = 123
输出：321

第一种算法

自己未看答案前自己写的。主要思路是：转成字符串逆序遍历，前面的0不拼接，如果有负号，最后再拼接到字符串前面，然后再将字符串转成整数。

def reverse1(x):
    if x == 0:
        return x
    s = str(x)
    n = len(s)
    rs = ""
    # 当出现第一位数字的时候，后面的0就需要添加上了
    add_zero = False
    for i in range(n):
        if s[n-1-i] != "0" and s[n-1-i] != "-":
            rs += s[n-1-i]
            add_zero = True
        if add_zero and s[n-1-i] == "0":
            rs += "0"

    if s[0] == "-":
        rs = "-" + rs

    if int(rs) < -(2 ** 31) or int(rs) > (2 ** 31 - 1):
        return 0
    else:
        return int(rs)

第二种算法

参考力扣精选答案和评论。我们只需要每次对 整数%10，就能得到末尾的数字，然后再将整数等于 整数/10 就能得到排除最后一位的新的整数。

def reverse2(x):
    n = 0
    ox = x
    x = abs(x)
    while x != 0:
        n = n * 10 + x % 10
        x = x // 10

    n = n if ox > 0 else -n
    if n < -(2 ** 31) or n > (2 ** 31 - 1):
        return 0
    else:
        return n

因为Python对于负数整除10的操作和别的语言不太一样，不方便计算，而且Python的底层是由C语言写的解释型语言，所以运行速度始终赶不上C语言它们。

最简单的C语言代码如下：

int reverse(int x)
{
    long n = 0;
    while (x)
    {
        n = n * 10 + x % 10;
        x /= 10;
    }
    return n > INT_MAX || n < INT_MIN ? 0 : n;
}

复杂度分析

• 时间复杂度：O(log(x))，x 中大约有 log 10 (x) 位数字。
• 空间复杂度：O(1)。