【5.3】LeetCode每日一题· 整数翻转

2021年05月03日 11时01分

标签： LeetCode 模拟数学

## 题目描述

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

如果反转后整数超过 32 位的有符号整数的范围 $$[-2^{32}, 2^{32}-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

#### 来源

> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/reverse-integer "题目链接")

## 解题思路

反转数字很简单，关键在于**如何在不使用64位整数的情况下，判断反转后的数字是否超过了32位整数的范围**。

设反转$$n$$次后，当前得到的已翻转部分的数字为$$res$$，下一个将要反转的数字为$$d$$。如果反转后的数字不超过32位整数范围，有

$$-2^{32} \leq res \times 10 + d \leq 2^{32}-1$$

记
$$INT\\_MAX = 2^{32}-1 = 2147483647 = \lfloor\frac{INT\\_MAX}{10}\rfloor+7$$

* 首先讨论不等式右边

1. 当

$$res < \lfloor\frac{INT\\_MAX}{10}\rfloor =214748364$$

时，即

$$res \leq \lfloor\frac{INT\\_MAX}{10}\rfloor =214748363$$

时，有

$$res\times10 \leq2147483630$$

而$$0\leq d\leq 9$$，因此

$$res\times 10 + d \leq 2147483630 + 9 \leq 2^{32}-1$$

一定成立。

2. $$res = \lfloor\frac{INT\\_MAX}{10}\rfloor = 214748364$$时，

$$res\times10 + d = 2147483640 + d$$，此时输入的$$x$$一定为$$\overline{d463847412}$$的形式，由于输入也一定在`int`范围内，即$$1463847412 \leq \overline{d463847412} \leq 2147483647$$，因此有$$d = 1$$，此时
   $$res\times10 + d = 2147483640 + d = 2147483641 < INT\\_MAX$$，
   等式成立。

3. $$res > \lfloor\frac{INT\\_MAX}{10}\rfloor = 214748364$$时，

$$res\times10 + d \geq 2147483650 + d = \overline{214748365d} > INT\\_MAX = 2147483647$$

因此，等式不成立。

综上，当$$res \leq \lfloor\frac{INT\\_MAX}{10}\rfloor$$时，有等式右侧成立。

* 再对不等式左边进行讨论。记

$$INT\\_MIN = -2147483648 = \lceil\frac{INT\\_MIN}{10}\rceil - 8 = -214783640 - 8$$

1. 当

$$res > \lceil\frac{INT\\_MIN}{10}\rceil = -214748364$$

时，即

$$res \geq \lceil\frac{INT\\_MIN}{10}\rceil = -214748363$$

时，有

$$res\times10 \geq -2147483630$$

而$$-9\leq d \leq 0$$，因此

$$res \times 10 + d \geq -2147483630 + d = -\overline{214748363(-d)} \geq INT\\_MIN=-2147483648$$

一定成立。

2. $$res = \lceil\frac{INT\\_MIN}{10}\rceil =-214748364 $$时，

$$res\times10 + d = -2147483640 + d= -\overline{214748364(-d)}$$，此时输入的$$x$$一定为$$-\overline{(-d)463847412}$$的形式，由于输入也一定在`int`范围内，即$$INT\\_MIN = -214748363 \leq -\overline{(-d)463847412} \leq -1463847412$$，

因此有$$d = -1$$，此时$$res\times10 + d = -2147483640 + d = -2147483641 \geq INT\\_MIN$$，等式成立。

3. $$res < \lceil\frac{INT\\_MIN}{10}\rceil =-214748364 $$时，

$$res\times10 + d \leq -2147483650 + d = -\overline{214748365(-d)} < INT\\_MIN = -2147483648$$

因此，等式不成立。

综上，当$$res \geq \lceil\frac{INT\\_MIN}{10}\rceil$$时，有等式右侧成立。

综上所述，当$$\lceil\frac{INT\\_MIN}{10}\rceil \leq res \leq \lfloor\frac{INT\\_MAX}{10}\\rfloor$$时，不等式成立。因此当对数字进行反转时，检查当前反转的数字是否在范围内即可，如果不在，则直接返回0。

注意，当$$res < 0$$的时候，C++中`(int)res`的值即为$$\lceil\frac{INT\\_MIN}{10}\rceil$$，`res % 10`的值为负数，和上述分析中$$d$$的符号与值相同。

## 代码

```c++
class Solution {
public:
    int reverse(int x) {
        if(x == 0) return 0;
        int res = 0;
        while(x){
            if(res > INT_MAX/10 || res < INT_MIN/10) return 0;
            res *= 10;
            res += x%10;
            x /= 10;
        }
        return res;
    }
};
```

## 用时和内存

> 执行用时：0 ms，在所有 C\++提交中击败了100.00%的用户
> 内存消耗：5.8 MB，在所有 C\++提交中击败了55.44%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【5.3】LeetCode每日一题· 整数翻转

所有评论

暂无评论

新增评论