[leetcode]7-整数反转

马谦马谦马谦

615
文章

17
评论

2020 年 2 月 10 日 11:13:24数据结构和算法评论133字数 590阅读 1 分 58 秒阅读模式

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/reverse-integer

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

示例：

输入: 123
输出: 321

示例 2：

输入: -123
输出: -321

示例 3：

输入: 120
输出: 21

二、题解

题目很简单，基本的思路就是对 n 循环取模，然后乘 10 累加。但是问题的关键点不是在这里，关键点是数据溢出。假设传入数据比 INT_MAX 小，但是反转后比 INT_MAX 大，那就会产生溢出。

INT_MAX = 2147483647, INT_MIN = -2147483648;

假设反转后的值是 output，被反转数字模 10 后得到 y，那么 output 应该被设置为 output * 10 + y 。

此时 output 溢出的条件：

output > INT_MAX / 10 或者 output = INT_MAX / 10 && y > 7 。
output < INT_MIN / 10 或者 output = INT_MIN / 10 && y < -8 。

以第一点为例，假设此时 output 大于最大值除以 10，那么它乘以 10 后肯定会大于最大值，也就会溢出。如果它等于最大值除 10，那么只要 y 大于最大值取模，也会溢出。

三、代码

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