算法学习-整数反转

 

题目和需求

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

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

常规解法

使用字符串回转方法(一般开发中的思路)

public static int reverse1(int x) {
        if (x == 0) {
            return 0;
        } else {
            String temp = String.valueOf(x);
            StringBuilder sb = new StringBuilder();
            int length = temp.length();
            if (x > 0) {
                for (int i = 0; i < length; i++) {
                    sb.append(temp.charAt(length - i - 1));
                }
                return Integer.valueOf(sb.toString());
            } else {
                for (int i = 0; i < length - 1; i++) {
                    sb.append(temp.charAt(length - i - 1));
                }
                return -Integer.valueOf(sb.toString());
            }
        }
    }

这个没有特殊技巧，就是一般实际工作中常见的思路，提出需求你，按需求思路解决需求。

改进算法

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

结题思路：

由于int反转后，可能会超过int最大值，所以使用long存储中间值，最后用强转后对比值大小判断是否有值溢出

从后往前，每次取到除以10的余数，每次循环一次，将上次所得值乘以10.

更多限制

不使用long,使用算数运算避免字符串操作

public static int reverse(int x) {
        if (x == 0) {
            return 0;
        } else {
            int ret = 0;
            while (x != 0) {
                int temp = ret;
                ret = (ret * 10) + (x % 10);
                if (temp != ret / 10)
                    return 0;
                x = x / 10;
            }
            return ret;
        }
    }

注意点：

if (temp != ret / 10)一定要在加法完成后计算是否越界
有些算法喜欢直接在上一步就比较是否大于int.maxvalue和小于int.minvalue,这是错的，因为java溢出继续添加，并不会报错，而是会继续进位。