leetcode之7-整数反转

java 里数字溢出

首先得搞明白，在 Java 里数字溢出会怎样？

我们知道：Java 中 int 类型是32位有符号（即包括正值和负值）的整数。所以它是有范围的，它的范围是 [-2 ^ 31, 2 ^ 31 - 1]。

那么，如果给它的最大值加一或者给他的最小值减一会发生什么事情呢？

通过实验可以看到两点：

1. Java 没有做数字溢出检测；
2. 最大值和最小值的关系好像一个循环，有点类似下图，顺时针是加操作，逆时针是减操作。

如何反转一个整数

可以类比于反转字符串。我们需要不断的从 x 中“pop”出最后一位数字，然后将它“push”到 res 的后面，直到 x 为空。

怎么做呢？当然可以将 x 转成 String 然后进行操作；也可以使用辅助堆栈或数组等的帮助来进行操作。

但是好像都比较麻烦，其实我们可以直接使用数学的方法来“pop”和“push”数字。

1.pop x 的最后一个数字
  pop = x % 10;
  x /= 10;
2.将 x 的最后一个数字 push 到 res 的后面
  temp = res * 10 + pop;
  res = temp;

官方题解

其实感觉这道题可以有好多种解法，甚至可以有各种骚思路，下面来一一介绍。

先来看看官方题解的思路吧。

不知道大家有没有注意到，上面将 x 的最后一个数字 push 到 res 的后面 temp = res * 10 + pop，这个式子其实是有潜在的溢出风险的。不过我们可以很容易的事先检查这个语句是否会导致溢出：

（1）假设 res 是正数：

1. 如果 temp = res * 10 + pop 会溢出，那么 res >= (temp - pop) / 10；
2. 如果 res > (temp - pop) / 10，那么 temp = res * 10 + pop 必定会溢出；
3. 如果 res = (temp - pop) / 10，那么只有当 pop > 7（其实就是 Integer.MAX_VALUE 的个位数）时，temp = res * 10 + pop 才会溢出

（2）同理可得，假设 res 是负数，只有当 pop < -8（其实就是 Integer.MIN_VALUE 的个位数）时，temp = res * 10 + pop 才会溢出。

所以事情就变得简单了，我们预先做好检查是否溢出就可以了。

/**
 * 官方题解
 */
public int reverse(int x) {
    int res = 0;
    while (x != 0) {
        int pop = x % 10;
        // 预先检查是否溢出
        if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && pop > Integer.MAX_VALUE % 10)) {
            return 0;
        }
        // 预先检查是否溢出
        if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && pop < Integer.MIN_VALUE % 10)) {
            return 0;
        }
        res = res * 10 + pop;
        x /= 10;
    }
    return res;
}

但是，再仔细深入想想：这道题给定的参数 x 本身就是合法的 int 值，而 int 的最大值和最小值开头的数字只能是 1 或 2，所以如果有最后一次循环的话，pop 的值一定是 1 或 2，因此 (res == INT_MAX / 10 && pop > 7) 和 (res == INT_MIN / 10 && pop < -8) 这两个判断肯定是不会成立的，可以省略。

/**
 * 官方题解代码优化
 */
public int reverse(int x) {
    int res = 0;
    while (x != 0) {
        int pop = x % 10;
        // 预先检查是否溢出
        if (res > Integer.MAX_VALUE / 10 || res < Integer.MIN_VALUE / 10) {
            return 0;
        }
        res = res * 10 + pop;
        x /= 10;
    }
    return res;
}

时间复杂度为 O(log(x))，因为 x 中大约有 lg(x) 位数字；空间复杂度为 O(1)。

骚操作一

将负数转为正数后再进行操作。

public int reverse(int x) {
    // 防止 -x 溢出报错
    if (x == Integer.MIN_VALUE || x == 0) {
        return 0;
    }
    // 如果是负数，转为正数处理，并将最后结果转为负数
    if (x < 0) {
        return -reverse(-x);
    }
    int res = 0;
    while (x != 0) {
        // 判断溢出。Integer.MAX_VALUE / 10 是 214748364，假如 res 大于 214748364，那么下面 res = res * 10 + x % 10 这一行就会溢出
        if (res > Integer.MAX_VALUE / 10) {
            return 0;
        }
        res = res * 10 + x % 10;
        x /= 10;
    }
    return res;
}

骚操作二

另类判断是否溢出。

前面说了，Java 没有做数字溢出检测，那如果溢出了，溢出后的值肯定就和原值就不一样了，所以也可以通过这一点来判断是否溢出。

public int reverse(int x) {
    int ans = 0;
    while (x != 0) {
        // 判断是否溢出
        if ((ans * 10) / 10 != ans) {
            return 0;
        }
        ans = ans * 10 + x % 10;
        x /= 10;
    }
    return ans;
}

骚操作三

转为 long 处理。

int 类型范围太小导致溢出了，那么我们就找个范围更大的类型来处理。

public int reverse(int x) {
    long result = 0;
    while (x != 0) {
        int pop = x % 10;
        result = result * 10 + pop;
        // 判断 int 类型是否溢出
        if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
            return 0;
        }
        x /= 10;
    }
    return (int) result;
}

骚操作四

转为字符串处理，不过也用到了 long 类型。

public int reverse(int x) {
    if (x == Integer.MIN_VALUE || x == 0) {
        return 0;
    }
    String strReverse = new StringBuilder(Integer.toString(Math.abs(x))).reverse().toString();
    long result = Long.parseLong(strReverse);
    // 负数转回负数
    if(x < 0) {
        result = -result;
    }
    // 判断 int 类型是否溢出
    if(result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
        return 0;
    }
    return (int) result;
}

骚操作五

利用第三方工具类。

虽然Java 没有做数字溢出检测，但是 JDK 提供的工具类或第三方提供的工具类都可以帮我们做这个检测。

比如在 JDK 中 Math 类的 addExact() 方法，比如 apache 的 org.apache.commons.math3.util.ArithmeticUtils 类中的 addAndCheck() 方法等。所以，捕捉溢出异常也可以。

public int reverse(int x) {
    int res = 0;
    while (x != 0) {
        try {
            res = Math.addExact(Math.multiplyExact(res, 10), x % 10);
            // 不能像下面这样写，因为 res * 10 已经溢出了
            // res = Math.addExact(res * 10, x % 10);
        } catch (ArithmeticException e) {
            return 0;
        }
        x /= 10;
    }
    return res;
}

凑字数

简简单单的一道题，只要动脑想，竟然可以有这么多不同的解法，是不是很神奇？

---