LeetCode7-ReverseInteger

LeetCodeeasyOverflow

题目

题目所在链接为 LeetCode-7:ReverseInteger

题目描述

给出一个32位的有符号整数, 反向输出一个整型数字

Given a 32-bit signed integer, reverse digits of an integer.

输入输出样例

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

备注

假设我们正在处理一个只能在32位有符号整数范围内存储整数的环境：[−2³¹, 2³¹ − 1]。出于此问题的目的，假设当反向整数溢出时，函数返回0.

Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2³¹, 2³¹ − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

例如 $2^{31} -1 = 2,147,483,647$ 如果设计的返回的值应该是$ 7,463,847,412 $ 溢出返回0 .

解题

解题思路

通过余数和除法获取从尾部获取数据的每一位,依次成将数据乘10 得到新的数据
判断符号, 判断是否溢出

时间复杂度: $ O(log(x)) $
空间复杂度: $ O(1) $

具体实现

class Solution {
public:
    int reverse(int x) {
        if (x == 0)
            return 0;
        // 输入long long 型 数据 避免溢出
        long long sum = 0;
        while (x!=0)
        {
            // 将每一位的数据 升位 加上余数
            sum = sum * 10 + x % 10;
            
            // 输入数字 降位
            x = x / 10;
            
            // 判断溢出
            if (sum > INT_MAX || sum < INT_MIN)
                return 0;
        }
        return int(sum);
    }
};

运行结果

使用C/C++实现
运行结果 2019-03-27

Runtime: 8 ms, faster than 99.38% of C++ online submissions for Reverse Integer.
Memory Usage: 8.2 MB, less than 99.80% of C++ online submissions for Reverse Integer.

改进优化

改进思路

题目底下最好的优化在了空间上的节省, 不用设置 long long 类型的数据, 采用int 型数据, 但是每次判断依次结果
很多数据会导致溢出直接抛弃掉可以节省大量的时间

整体流程如下:

如果结果会溢出, 如果是正值则 $temp = rev*10+pop $ 则
$$ rev > frac{INTMAX}{10} || (rev == frac{INTMAX}{10} && pop>7) $$
如果结果会溢出, 如果是负值则 $temp = rev*10+pop $ 则
$$ rev <> frac{INTMIN}{10} || (rev == frac{INTMIN}{10} && pop<-8) $$
其中 $ pop = x%10 $

改进的实现

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

运行结果

Runtime: 4 ms, faster than 100.00% of C++ online submissions for Reverse Integer.
Memory Usage: 8.1 MB, less than 99.80% of C++ online submissions for Reverse Integer.