leetCode–整数反转

题目描述：

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-integer

题目分析

• 看到反转我们应该想到可以将数字转换为字符串进行解题，不过要分情况讨论

• 题目中说：假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^{31}−231, 2^{31} − 1231−1] 可以理解为：

​ ①不能够使用长整形long；

​ ②可以使用长整形long，需要解释什么情况下返回值为0；

• 综合上面的分析，给出以下三种解法。

一.字符反转法

思路分析

1. 输入为0的时候，直接返回输入值；
2. 不为0的时候，先将输入的数字用StringBuilder转化为字符串后进行反转。
3. 从反转后的字符串中返回“-”的索引，
4. 如果索引不为-1，则说明反转后的数字是有符号的
5. 如果有符号，则将末尾符号删去，添加到前面
6. 无符号或者删去符号后的字符串转化为长整型会自动消去前面的0
7. 然后判断是否越界
8. 最后强转为int类型返回

解题代码

class Solution {
    public int reverse(int x) {
       if(x != 0){
        long fNum = 0;
        StringBuilder builder = new StringBuilder();
        builder.append(x).reverse();
        int i = builder.indexOf("-");
        if(i != -1){
            builder.deleteCharAt(i);
            builder.insert(0,"-");
        }
        fNum = Long.parseLong(builder.toString());
        return (int)fNum == fNum ?(int)fNum : 0;
       }else{
           return x;
       }
    }
}

测试结果

二.忽略Long限制

解题思路

1. 首先文字上限制我们只能使用 3232 位的数据结构（int）。
2. 由于数据范围过大，使用 int 会有溢出的风险，所以我们使用 long 来进行计算，在返回再转换为 int。
3. 当输入值不为0时候，利用10取余取得最后的一位数字 比如:123%10–>3
4. 再利用整除10获得剩下的整数然后赋值给输入值，比如：123/10–>12
5. 循环下去直到输入值等于0
6. 然后强转长整型，判断是否溢出，如果溢出返回0，否则返回该值

解题代码

原代码：

class Solution {
    public int reverse(int x) {
        long flag = 0;
        long result = 0;
        while (x != 0) {
            flag = x % 10;
            result = result * 10 + flag;
            x = x / 10;
        }
        return (int)result == result ? (int)result : 0;
    }
}

变量有点多啊，减少一个！

修改后：

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

测试结果

原测试：

修改后：

三.先判断限制

解题思路

1. 先直接判断输入是否为0，如果为0直接返回，否则进入循环
2. 其中Integer.MAX_VALUE值为2147483647，Integer.MIN_VALUE值为-2147483648
3. 循环后判断是否溢出，溢出的话直接返回0
4. 否则反转后返回，反转的思路一样是用取余和整除

解题代码

源代码：

class Solution {
    public int reverse(int x) {
        int flag = 0;
        while (x != 0) {
            //如果反转后不溢出，那么则一直不会进入到if判断里面
            if (x > 0 && flag > (Integer.MAX_VALUE - x % 10) / 10){
                return 0;
            } 
            if (x < 0 && flag < (Integer.MIN_VALUE - x % 10) / 10){
                return 0;
            } 
            flag = flag * 10 + x % 10;
            x /= 10;
        }
        return flag;
    }
}

优化一下：

class Solution {
    public int reverse(int x) {
        int flag = 0;
        while (x != 0) {
            if (x > 0 && flag > Integer.MAX_VALUE / 10) return 0;
            if (x < 0 && flag < Integer.MIN_VALUE / 10) return 0;
            flag = flag * 10 + x % 10;
            x /= 10;
        }
        return flag;
    }
}

测试结果

源代码：

优化后：