LeetCode 7. Reverse Integer

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 7. Reverse Integer 原题链接简单

作者：

yxc , 2018-04-13 01:56:07 , 所有人可见 , 阅读 5633

11

2

题目描述

给定一个int型整数，请将各位数字反转。
如果结果大于INT_MAX或小于INT_MIN，请返回0.

注意：

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 $[−2^{31}, 2^{31} − 1]$。请根据这个假设，如果反转后整数溢出那么就返回 0。

样例1

输入： 123
输出： 321

样例2

输入：-123
输出：-321

样例3

输入：120
输出：21

算法

(循环) $O(log n)$

依次从右往左计算出每位数字，然后逆序累加在一个整数中。
另外，这题有两点需要注意：

因为int型整数逆序后可能会溢出，所以我们要用long long记录中间结果；
在C++中，负数的取模运算和数学意义上的取模运算不同，结果还是负数，比如 $-12 \% 10 = -2$，所以我们不需要对负数进行额外处理。

时间复杂度分析：一共有 $O(log n)$ 位，对于每一位的计算量是常数级的，所以总时间复杂度是 $O(log n)$.

C++ 代码

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

18 评论

柠檬鱼泡秋刀茶_8 2023-04-01 14:55

想请教一下，res > (INT_MAX - x % 10) / 10中的/号不会丢失精度吗？

夜神月 2022-05-11 18:36

这样也能过。。

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