题目内容

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

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

题解

本题可以依次从右往左计算出每位数字，然后逆序累加在一个整数中。

本题有两点需要注意：
1、由于int型整数逆序后可能会溢出，要用long long类型记录中间结果；
2、在C++中，负数的取模运算和数学意义上的取模运算不同，其结果还是负数，例如 −12 % 10 = −2，所以我们不需要对负数进行额外处理。

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

解释一下为什么O(logn):
比如数字n=100，那其数字长度与 log以10为底的100的对数 有关。本题中更关心的是数x，对应的数字长度。

代码

class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while(x){
            //x % 10 把x的每一位抠出来,然后再更新x=x/10即可。 秦九韶算法
            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 = x/10;
        }
        return res;
    }
};