LeetCode-整数反转（007）

一.题目描述

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

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

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

二.示例

示例 1：

输入：x = 123
输出：321

示例 2：

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

示例 3：

输入：x = 120
输出：21

示例 4：

输入：x = 0
输出：0

三.提示：

-231 <= x <= 231 - 1

四.解法:

方法一：数学

我们不妨记 mi 和 mx 分别为 −231 和 231−1，则 x 的反转结果 ans 需要满足 mi≤ans≤mx。

我们可以通过不断地对 x 取余来获取 x 的最后一位数字 y，并将 y 添加到 ans 的末尾。在添加 y 之前，我们需要判断 ans 是否溢出。即判断 ans×10+y 是否在 [mi,mx] 的范围内。

若 x>0，那么需要满足 ans×10+y≤mx，即 ans×10+y≤⌊mx10⌋×10+7。整理得 (ans−⌊mx10⌋)×10≤7−y。

下面我们讨论上述不等式成立的条件：

当 ans<⌊mx10⌋ 时，不等式显然成立；
当 ans=⌊mx10⌋ 时，不等式成立的充要条件是 y≤7。如果 ans=⌊mx10⌋ 并且还能继续添加数字，说明此时数字是最高位，即此时 y 一定不超过 2，因此，不等式一定成立；
当 ans>⌊mx10⌋ 时，不等式显然不成立。

综上，当 x>0 时，不等式成立的充要条件是 ans≤⌊mx10⌋。

同理，当 x<0 时，不等式成立的充要条件是 ans≥⌊mi10⌋。

因此，我们可以通过判断 ans 是否在 [⌊mi10⌋,⌊mx10⌋] 的范围内来判断 ans 是否溢出。若溢出，则返回 0。否则，将 y 添加到 ans 的末尾，然后将 x 的最后一位数字去除，即 x←⌊x10⌋。

时间复杂度 O(log⁡|x|)，其中 |x| 为 x 的绝对值。空间复杂度 O(1)。

五.代码

Java代码

class Solution {
    public int reverse(int x) {
        // 初始化结果变量
        int ans = 0;
        
        // 循环处理每一位数字
        for (; x != 0; x /= 10) {
            // 检查是否会导致溢出
            if (ans < Integer.MIN_VALUE / 10 || ans > Integer.MAX_VALUE / 10) {
                return 0;
            }
            
            // 将当前位添加到结果中
            ans = ans * 10 + x % 10;
        }
        
        // 返回反转后的整数
        return ans;
    }
}
注释说明
    ·初始化结果变量：ans 用于存储反转后的整数。
    ·循环处理每一位数字：通过 x /= 10 不断缩小 x，逐位处理。
    ·溢出检查：在每次更新 ans 之前，检查 ans 是否会在下一步操作中溢出。
        ·如果 ans 小于 Integer.MIN_VALUE / 10 或大于 Integer.MAX_VALUE / 10，则反转后的结果会溢出，返回 0。
    ·更新结果：将当前位的数字添加到 ans 中。
    ·返回结果：返回反转后的整数。