题目描述

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

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

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

样例1

输入：x = 123
输出：321

样例2

输入：x = -123
输出：-321

样例3

输入：x = 120
输出：21

样例4

输入：x = 0
输出：0

提示

• $-2^{31} <= x <= 2^{31} - 1$

算法1

(数学 + 使用long类型)

• 这题涉及两个很经典的操作：
  1. 给定一个数x，从低到高依次分解出每一位的数字a：a = x % 10; x /= 10
  2. 从高到低依次给出每一位数a，还原出原来的数x：x = x * 10 + a

• 由于溢出的可能，我们直接用64位的长整型变量存储中间结果，如果发现溢出则直接返回0

• 时间复杂度：$O(logx)$, x是十进制的位数

• 空间复杂度：$O(1)$

Java 代码

class Solution {
    public int reverse(int x) {
        long res = 0;
        while(x != 0){
            res = res * 10 + x % 10;
            if(res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) {
                return 0;
            }
            x /= 10;
        }
        return (int)res;
    }
}

算法2

(数学 + 不使用long类型)

• 观察算法1，发现如果发生溢出，一定是res = res * 10 + x % 10;这条语句导致的
  1. x为正数，res * 10 + x % 10 > MAX移项得res > (MAX - x % 10) / 10
  2. x为负数，res * 10 + x % 10 < MIN移项得res < (MIN - x % 10) / 10

• 每次循环时通过以上不等式判断是否溢出即可

• 时间复杂度：$O(logx)$, x是十进制的位数

• 空间复杂度：$O(1)$

Java代码

class Solution {
    public int reverse(int x) {
        int res = 0;
        while(x != 0){
            if(x > 0 && res > (Integer.MAX_VALUE - x % 10) / 10) return 0;
            if(x < 0 && res < (Integer.MIN_VALUE - x % 10) / 10) return 0;
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
}