0007. 整数反转

0007. 整数反转 #

  • 标签：数学
  • 难度：中等

一、题目说明 #

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

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

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

示例

  • 示例 1：
输入：x = 123
输出：321
  • 示例 2：
输入：x = -123
输出：-321
  • 示例3：
输入：x = 120
输出：21
  • 示例4：
输入：x = 0
输出：0

提示

  • $-2^{31} <= x <= 2^{31} - 1$

二、解题思路 #

1. 商数余数法 #

想要反转一个数字，就是将这个数字的最低位放到最高位，次低位放到次高位……直至最高位放到最低位，那么就要求：

  • 由低位到高位，除以10依次拆解每一个数字；

  • 由高位到地位，乘以10依次组合每一个数字；

例如：

先拆解一个数字1347：

  • 第一步，先用1347除以10，得商134余数7，这样就获取了第一位数字7；

  • 第二步，用上一步的商134再除以10，得商13余数4，这样就获取了第二位数字4；

  • 第三步，用上一步的商13再除以10，得商1余数3，这样就获取了第三位数字3；

  • 第四步，用上一步的商1再除以10，得商0余数1，这样就获取了第四位数字1；

  • 最终，得到的数字顺序为7、4、3、1。

然后再组合：

  • 第一步，先用0乘以10，再加上第一个数字7，和为7；

  • 第二步，再用第一步的和7乘以10，再加上第二个数字4，和为74；

  • 第三步，再用第一步的和74乘以10，再加上第三个数字3，和743；

  • 第四步，再用第三步的和743乘以10，再加上第四个数字1，和7431；

这样，就完成了一个数字的反转。

但是由上面的题意可以知道，本题要求我们不能使用long类型的变量来承接反转后的数字，那么就需要考虑int类型的范围问题。

比如原数字1234567889，反转后就变成了9887654321，远远超出了Integer.MAX_VALUE（大约21亿多），按题目要求需要返回0，负数同理。

所以需要在组合的过程中，时时刻刻关注此时的结果大小：

  • 如果是正数，且此时已经大于214748364，那么后面若还有正数求和，必然溢出；或者此时已经等于214748364，后面的数字大于7，也会溢出；

  • 如果是负数，且此时已经小于-214748364，那么后面若还有负数求和，必然溢出；或者此时已经等于-214748364，后面的数字小于-8，也会溢出；

public int reverse(int x) {
    int result = 0;
    while(0 != x){
        int remainder = x % 10;
        //正数
        if(result>Integer.MAX_VALUE/10 || result==Integer.MAX_VALUE/10 && remainder>Integer.MAX_VALUE%10){
            return 0;
        }
        //负数
        if(result<Integer.MIN_VALUE/10 || result==Integer.MIN_VALUE/10 && remainder<-Integer.MIN_VALUE%10){
            return 0;
        }
        x /= 10;
        result = result * 10 + remainder;
    }
    return result;
}