【算法】Reverse Integer

1. 概述

LeetCode7: https://leetcode.com/problems/reverse-integer/

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

2. 思路

题目的要求是给定一个整数，将其数字位反转后返回。

这题考察的点就是对溢出的处理。整型数的范围是 -2147483648 ~ 2147483647，因此这道题就是考察的翻转过后超出了这个范围之后的处理。

我们可以从右到左依次获取数字，并挨个加到返回结果上。如果在这个过程中出现了溢出，那么就返回0。

溢出情况的处理，这里会有两种溢出的情况：

1. 如果是个正数，那么就需要跟 2147483647 / 10 比较，如果比它大，那么再乘10加新的数位就一定会溢出；如果等于 2147483647 / 10，那么需要看所加的数，如果大于7也会溢出，因为2147483647的最后一位就是7，如果2147483647 / 10再加上一个大于7的数，必然大于2147483647，那么就溢出了，返回0；
2. 如果是个负数，那么就需要跟-2147483648 / 10比较，如果比它小，那么再乘10加新的数位就一定会向下溢出；如果等于-2147483648 / 10，那么需要看所加的数，如果小于-8也会溢出，因为2147483648的最后一位就是8，如果 -2147483648 / 10 再加上一个小于-8的数，那么必然就会小于-2147483648，就向下溢出了，返回0.

3. 代码和测试

Java

package cn.pku.edu.algorithm.leetcode.day01;

/**
 * @author allen
 * @date 2022/9/18
 */
class Solution {
    public int reverse(int x) {
        int res = 0;
        while (x != 0) {
            int num = x % 10;
            x = x / 10;
            if ((res > Integer.MAX_VALUE / 10) || (res == Integer.MAX_VALUE / 10 && num > 7)) {
                return 0;
            }
            if ((res < Integer.MIN_VALUE / 10) || (res == Integer.MIN_VALUE / 10 && num < -8)) {
                return 0;
            }
            res = res * 10 + num;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

C++

class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while (x != 0) {
            int num = x % 10;
            x = x / 10;
            if (res > INT_MAX / 10 || (res == INT_MAX / 10 && num > 7)) {
                return 0;
            }
            if (res < INT_MIN / 10 || (res == INT_MIN / 10 && num < -8)) {
                return 0;
            }
            res = res * 10 + num;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18