LeetCode7-整数反转

发表于 | 分类于

题目链接

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

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

题目详述

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

示例 1:

1
2
输入: 123
输出: 321

示例 2:

1
2
输入: -123
输出: -321

示例 3:

1
2
输入: 120
输出: 21

注意:

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

题目详解

反转整数的基本过程如下：

1
2
3
4
5
int r = 0;
while (r < x) {
    r = 10 * r + x % 10;	// 这一步可能溢出
    x /= 10;
}

在反转整数的过程中可能会溢出，对此有两种解决方案。

  • 方案一：先判断是否会溢出，再计算。
  • 方案二：先计算，再判断是否已溢出。

基于方案一的解法：

  • 首先对输入进行正负判断（因为正数和负数的溢出的极限值不同，分别为 2147483647、-2147483648）。
  • 对于正数，如果在计算之前发现当前值 r > 214748364 或 r == 214748364 && t > 7，那么会溢出，返回 0。
  • 对于负数，如果在计算之前发现当前值 r < -214748364 或 r == -214748364 && t < -8，那么会溢出，返回 0。
  • 没溢出就继续计算直至返回正确的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class LeetCode_00007 {

    public static int reverse(int x) {
        int r = 0;
        if (x > 0) {
            int m = Integer.MAX_VALUE / 10;
            while (x != 0) {
                int t = x % 10;
                x /= 10;
                if (r > m || (r == m && t > 7)) {
                    return 0;
                }
                r = r * 10 + t;
            }
        } else if (x < 0) {
            int m = Integer.MIN_VALUE / 10;
            while (x != 0) {
                int t = x % 10;
                x /= 10;
                if (r < m || (r == m && t < -8)) {
                    return 0;
                }
                r = r * 10 + t;
            }
        }
        return r;
    }
}

基于方案二的解法：

  • 先计算得到 int tmp = r * 10 + t;。
  • 再通过比较 (tmp - t) / 10 与 r 判断是否已经溢出，没有溢出是可以还原的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LeetCode_00007 {

    public static int reverse(int x) {
        int r = 0;
        while (x != 0) {
            int t = x % 10;
            int tmp = r * 10 + t;
            if ((tmp - t) / 10 != r) {
                return 0;
            }
            x /= 10;
            r = tmp;
        }
        return r;
    }
}