精选50 题之 7. 整数反转

落日映苍穹つ 2024-04-17 16:53 51阅读 0赞

### 腾讯精选练习（50 题）之 7. 整数反转 ###

*   *  原题目链接
     *  题目分析
     *  解题思路
     *  代码实现
     *  优化

## [原题目链接][Link 1] ##

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:

输入: 123  
输出: 321  
示例 2:

输入: -123  
输出: -321  
示例 3:

输入: 120  
输出: 21  
注意:  
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为\[-2ˆ31, 2ˆ31-1\]。请根据这个假设，如果反转后整数溢出那么就返回 0。

## 题目分析 ##

这是50题中第一道简单题。  
反转整数的思路是从一个数的最后一位开始，依次向前遍历。

## 解题思路 ##

尾数通过取余得到，整除10清除已得到尾数，循环直至原数为空。

## 代码实现 ##

C++

class Solution {
        
    public:
        int reverse(int x) {
        
        // 需使用long int，否则若在循环中出现溢出，会在if判断临界前报错
        long int result = 0; 
        int j = x;
        while(j)
        {
        
            result = 10*result + j%10;
            j = j/10;
        }
        if(result < INT_MIN || result > INT_MAX) //如果大于或者小于临界值，返回0
        {
        
            return 0;
        }
        return result;
        }
    };

![实现1][1]  
要注意的是：乘10累加的过程中就有可能溢出，所以可以选择使用 *long int* 进行存储，再在后面进行判断是否相对int型越界。  
32位编译系统：int占四字节，与long相同，均为\[-2ˆ31, 2ˆ31-1\]。  
64位编译系统：int占四字节，long占8字节，long数据范围变为：\[-2ˆ63, 2ˆ63-1\]。

## 优化 ##

引入long int，是避开了计算过程中对溢出的讨论，并不是必须的。

那么，在计算过程中判断即时判断溢出就可以作为优化的切入点。

因为 r e s u l t = ( r e s u l t o l d ) ∗ 10 + p o p result = (resultold)\*10+pop result=(resultold)∗10\+pop  
以正数为例  
 r e s u l t o l d > = ( I N T M A X ) 10 时 ， 就 可 能 出 现 会 越 界 resultold >= \\frac\{(INTMAX)\}\{10\}时，就可能出现会越界 resultold>=10(INTMAX)时，就可能出现会越界  
具体来讲，  
 ① r e s u l t o l d > ( I N T M A X ) 10 ， 无 论 p o p 为 任 何 值 都 会 越 界 ①resultold > \\frac\{(INTMAX)\}\{10\}，无论pop为任何值都会越界 ①resultold>10(INTMAX)，无论pop为任何值都会越界  
 ② r e s u l t o l d = = ( I N T M A X ) 10 ， p o p > = 7 就 会 越 界 ②resultold == \\frac\{(INTMAX)\}\{10\}，pop>=7就会越界 ②resultold==10(INTMAX)，pop>=7就会越界

同理，当输入为负数时  
 ① r e s u l t o l d > ( I N T M I N ) 10 ， 无 论 p o p 为 任 何 值 都 会 越 界 ①resultold > \\frac\{(INTMIN)\}\{10\}，无论pop为任何值都会越界 ①resultold>10(INTMIN)，无论pop为任何值都会越界  
 ② r e s u l t o l d = = ( I N T M I N ) 10 ， p o p < = − 8 就 会 越 界 ②resultold == \\frac\{(INTMIN)\}\{10\}，pop<=-8就会越界 ②resultold==10(INTMIN)，pop<=−8就会越界

所以修改代码中的判断规则，代码如下：

class Solution {
        
    public:
        int reverse(int x) {
        
            int result = 0;
            const int MAX = INT_MAX/10;
            const int MIN = INT_MIN/10; 
            int pop = 0;
            while (x != 0) {
        
              
                pop = x % 10;
                x /= 10;
     
                if (result > MAX || (result == MAX && pop > 7)) return 0;
                if (result < MIN || (result == MIN && pop < -8)) return 0;
                result = result * 10 + pop;
            }
            return result;
        }
    };

![实现2][2]

提升效果显著

[Link 1]: https://leetcode-cn.com/problems/reverse-integer/submissions/
[1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/ea05dd308bda44bcae95ae6a04a8d602.png
[2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/71b59df70d2a44ac804cad7154fc5808.png