4.整数反转

发表于 | 分类于 | 阅读次数

题目

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。如果反转后整数溢出那么就返回 0。

如123->321 , 120->21 , -123->-321

题解

算法思路:除运算(/)+模运算(%)

除数10 （1）相除取整x （2）取余pop （3）对取模结果累计 result
第一次循环-> 1234/10=123 1234%10=4 0*10+4=4
第二次循环-> 123/10=12 123%10=3 4*10+3=43
第三次循环-> 12/10=1 12%10=2 43*10+2=432
第四次循环-> 1/10=0 1%10=1 432*10+1=4321
0—>不再循环

关键点：除数是10，当算出一位数字pop，就会将当前result * 10+pop，并不是对4、3、2、1最后来计算(不是4 * 1000+3*100···)

溢出情况考虑：

int类型：4字节，4*8=32bit(1字节=8bit)。取值范围
[−2^31, 2^31 − 1] -> java中为Integer.MIN_VALUE , Integet.MAX_VALUE。

  • 在对当前计算结果result*10+pop操作前判断是否溢出。
  • command键+鼠标移至Integet.MAX_VALUE，可看到最大值：2147483647，Integer.MIN_VALUE：-2147483648。

溢出条件1：：result*10+pop > MAX_VALUE。

  • （1）result>MAX_VALUE / 10。一定溢出
  • （2）result=MAX_VALUE / 10，且pop>7(7为最后一位，=Integet.MAX_VALUE%10)
  • 溢出条件2：*：result*10+pop<MIN_VALUE
  • （1）result<MIN_VALUE / 10。一定溢出
  • （2）result=MIN_VALUE /10，且pop<-8(-8 = Integet.MIN_VALUE%10)

关键点：
判断溢出，是与极值/10进行比较。并非拿result10来与极值比较，因为在比较前，result10可能就已经溢出了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    private int reverse(int x) {
        int result = 0;
        while (x != 0) {
            int pop = x % 10;
            if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && pop > 7)) {
                return 0;
            }
            if (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && pop < -8)) {
                return 0;
            }
            result = result * 10 + pop;
            x = x / 10;
        }
        return result;
    }
}

代码优化

对于溢出条件，

  • （1）result == Integer.MAX_VALUE / 10时，pop>7条件可省略：若pop大于7，相当于此时x第一位为7，这是x已溢出（int类型极值首位是2）。此种情况不存在。
  • （2）同理，result == Integer.MIN_VALUE / 10 时，pop<-8条件可省略。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    private int reverse(int x) {
        int result = 0;
        while (x != 0) {
            int pop = x % 10;
            if (result >= Integer.MAX_VALUE / 10) {
                return 0;
            }
            if (result <= Integer.MIN_VALUE / 10) {
                return 0;
            }
            result = result * 10 + pop;
            x = x / 10;
        }
        return result;
    }
}

其他想法：

  • 字符串的反转方法。

StringBuilder的reverse()。这比较适用于字符串的反转，而非整数，效率低。

1
2
3
4
5
6
7
8
9
10
11
12
13
private int reverse(int x) {
    boolean addFlag = x < 0;
    x = Math.abs(x);
    String str = String.valueOf(x);
    str = new StringBuilder(str).reverse().toString();
    try {
        x = Integer.parseInt(str);
    } catch (Exception e) {
    //若溢出，catch异常，返回0
        return 0;
    }
    return addFlag ? 0 - x : x;
}
  • Math.abs()。

自己写代码实现时，并未考虑到负数求模，想着若<0,先取绝对值，这个逻辑并不好。

若x=Integer.MIN_VALUE(-2147483648),Math.abs(x)->返回原值MIN_VALUE，仍为负。（在数学中，绝对值会为2147483648，这里超出int类型最大值）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int reverse(int x) {
    boolean a = x >= 0;
    x = Math.abs(x);
    int result = 0;
    int limit = Integer.MAX_VALUE;
    while (x > 0) { //注意这里是>0，并非之前的!=0;
    //因为x若为MIN_VALUE，取绝对值后仍未负，可直接返回0。
        if (result > (limit / 10)) {
            return 0;
        }
        result = result * 10 + x % 10;
        x = x / 10;
    }
    return a ? result : 0 - result;
}

题目：力扣No.7 整数反转