【每日一题 - LeetCode 热题 HOT 100 - 7. 整数反转】

1.题目

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

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321
示例 2：

输入：x = -123
输出：-321
示例 3：

输入：x = 120
输出：21
示例 4：

输入：x = 0
输出：0

2. 思路一

一看到这个题很容易让人想到用字符串的方法，因为有负号，有超范围的大数字，只需要转换成字符串类型，然后String.reverse()即可解决。

值得注意的是：转成String会有NumberFormatException

代码如下：

    public static int reverse(int x) {
        try {
            String x_str = String.valueOf(x);

            if (x < 0) {
                x_str = x_str.substring(1);
            }
            StringBuffer sb = new StringBuffer(x_str);
            sb.reverse();
            if (x < 0) {
                sb.insert(0, '-');
            }
            int y = Integer.parseInt(sb.toString());
            return y;
        }
        catch (NumberFormatException e){
            return 0;
        }
    }

这种方法大多数都能想到，但是这种方法很明显完全没有算法的意义，时间复杂度和空间复杂度都比较高，如下图所示：

3. 思路二

还有一种方式大家也很容易想到，就是对10循环取余，然后将取下来的余数循环乘10，同时原数字缩小10倍(除10)。代码如下：

    public static int reverse(int x) {
        long y = 0;
        while (x!=0){
            y = y*10 + x%10;
            x = x / 10;
        }
        return (int)y==y? (int)y:0;
    }

这种方式速度非常快，如下：

4. 参考

1. https://leetcode.cn/problems/reverse-integer/