云野 ☁️

13、整数反转

|
|
访问
本文共717字。
展开

题目描述

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321
链接：https://leetcode-cn.com/problems/reverse-integer

错误案例

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def reverse(self, x: int) -> int:
        a = 0
        while x!=0:
            if x<0:
                b = x % 10 - 10  # 想解决负数输入情况，但末尾=0时不行，见特殊情况
                x = x // 10 + 1  # 想解决负数情况，但末尾=0时不行。
            else:
                b = x % 10
                x //= 10
            a = a * 10 + b 
        return a

注：/除法；//除法向下取整。 1423/10=142.3; 1423//10=142

特殊情况

正数取余 % 返回末尾数字，如123%10=3；但负数取余 %，返回[0,9)数字，如-123%10=7。（想得到末尾-3，但是不能单纯的-10）。因为当末尾本身就是0，无论正负返回还是0。如-100%10=0。-10 就错了。

取模：% 返回除法的余数。

当数字<0 and 末尾!=0时，-123%10-10=-3.

1
2
3
4
5
6
7
8
9
10
class Solution:
    def reverse(self, x: int) -> int:
        a = 0
        while x!=0:
            b = x % 10
            if x<0 and b != 0:  # 负数，且末尾不为0时
                b = x % 10 - 10
            x = (x-b) // 10  # 取整。-b去掉末尾数的影响。
            a = a * 10 + b 
        return a

取整。-b去掉末尾数的影响：123//10=12; -123//10=-13（X）。去掉末尾数的影响，(123-3)//10=12; (-123-(-3))//10=-12。即(x-b) // 10

题中还有一个条件：超过 32 位的有符号整数的范围 [−2^31^, 2^31^ − 1] ，就返回 0。于是改进如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def reverse(self, x: int) -> int:
        MIN, MAX = -2**31, 2**31-1
        a = 0
        while x!=0:
            b = x % 10
            if x<0 and b != 0: 
                b = x % 10 - 10
            x = (x-b) // 10 
            a = a * 10 + b 
        if a<MIN or a>MAX:  # 判断有无超过32位
   			return 0
        return a

但是环境不允许存储 64 位整数（有符号或无符号）。也就是说a已经超过了32位，不能直接存储并和MAX，MIN比较大小。

尽量不要对边界进行加减，以防越界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def reverse(self, x: int) -> int:
        MIN, MAX = -2**31, 2**31-1
        a = 0
        while x!=0:
            b = x % 10
            if a > MAX//10 or (a == MAX//10 and b > 7):  # 只需要比较前九位
                return 0
            if a < (MIN+8)//10 or (a == (MIN+8)//10 and b < -8):  # 负数向下取整的问题，排除末尾的影响。
                return 0
            if x<0 and b != 0:
                b = x % 10 - 10
            x = (x-b) // 10
            a = a * 10 + b 
        return a

MIN = -2147483648

MAX = 2147483647

只需要比较：前九位。

时间复杂度：O(log|x|)。翻转次数即x十进制的位数。（看不懂…)

空间复杂度：O(1)