整数反转 Reverse Integer

题目

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

以下为详细说明:

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note:

Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

思路&题解

intro

算法题中有很多都是做一些反转处理,本题要求对32位有符号整型数字反转,符号不必处理。

思路为从低位开始,按位提取数字,并赋值给中间量,赋值过程从高位开始。 整个算法的关键点是,对整型溢出的预判逻辑,虽然算法核心逻辑清晰,如果忽略了溢出的限制,此题是解答不成功的。

整型翻转.png

public class Solution {
    public int reverse(int x) {
        int min = -1<<31;
        int max = -min - 1;
        int result = 0;
        while(x != 0) {
            // 取余数,相当于获取低位数值
            int rightPart = x%10;
            // 易错点:除以10,相当于移动最低位,
            x /= 10;
            // 易错点:此处可能会溢出
            //result = result * 10 + rightPart;
            if (result > max/10 || (result == max/10 && rightPart > 7)) {
                return 0;
            }
            if (result < min/10 || (result == min/10 && rightPart < -8)) {
                return 0;
            }
            result = result * 10 + rightPart;
        }
        return result;
    }
}

知识点分析

梳理一下这题的几个知识点。

  • 逐位处理

对一个整型,按位处理,一种方式是可以转换为字符串,从而根据索引处理每一位的数字。

另一种就是直接进行数值运算,整型的基数是10,因此可以从进位规则下手。 除以10得到的余数就是个位数的数值,计算完个位数后,我们把原数值去除各位后,得到新的数值,再次循环计算各位数值;整个过程即是按位处理。

tmp = x%10

  • 位增减处理

按位处理有一个步骤,就是讲原数字去除个位,得到新的数值。这里,注意严谨,不要犯常识错误,比如通过减法,原数字减去个位数得到新数值,当个位数是0时得不到正确的结果,比如10-0=10;正确的做法是除以是10,去结果即可。

x /= 10

  • 整型溢出原理

本题中,整型是32位数字,提示信息中已经告诉我们最新小值是-2^31,最大值是2^31-1

所谓溢出,笔者的理解是:计算机本来用32位的变量来表示的这个整型,但是接受到的数值超出了32位,位置不够,放不下了,那么就产生了溢出,溢出的具体处理可能各异。比较常见的有舍弃高位,假设接受位数是3,那么针对二进制的1000已经超出以为,舍弃高位后变成二进制的000。也有些是直接报错异常的。

那么在本题中,判断溢出的操作有两个if逻辑块,为甚么会出现7-8呢?

这个问题也困扰了我好一会儿。我们回归到溢出的语句分析一下:

// 易错点:此处可能会溢出
result = result * 10 + rightPart;
  1. 如果上述语句溢出,由于rightPart是取值为[0,9],不可能溢出,因此溢出的一定是result * 10
  2. 如果result * 10溢出,则result * 10 >= max 或者 result * 10 =< min,等于不一定会溢出,需要结合rightPart的取值;

情况一:

  1. 如果result * 10 >= max,则result >= max/10
  2. result > max/10时,一定是溢出的
  3. result == max/10时,需要结合rightPart,即两者只和如果大于max就溢出
  4. 因为max的个位数是7,所以rightPart > 7时溢出
  5. 整合起来就是第一个if的逻辑块

情况二:

  1. 如果result * 10 <= min,则result <= min/10
  2. result < min/10时,一定是溢出的
  3. result == min/10时,需要结合rightPart,即两者只和如果小于min就溢出
  4. 因为min的个位数是8,所以rightPart < -8时溢出
  5. 整合起来就是第二个if的逻辑块

如何知道max和min的个位数是多少?

这个确实可能记不住,记不住完全没关系,可以通过代码输出,直接用动态计算替代即可:

System.out.println("max = " + max + "," + Integer.toBinaryString(max) + ", "+ max%10);
System.out.println("min = " + min + "," + Integer.toBinaryString(min) +","+min%10);

输出

max = 2147483647,1111111111111111111111111111111, 7
min = -2147483648,10000000000000000000000000000000,-8
powered by Gitbook© 小文字 更新: 2019-04-10

results matching ""

    No results matching ""