Leetcode 整数反转 (002)

前言

基础题

注释完善源码获取

整数反转

其实一开始我没看太懂题目,其实就是给一个整数,反转过来去掉0,当然不能越界。 1.png

思考解题

解法很多种,比如转化为字符串,判断“-”,倒转即可

public static int reverse(int x){
          //先将字符串转为数字,并取绝对值
          long kk = x;
          long kk2 = Math.abs(kk);
          // 将取绝对值之后的数字转化为字符串
          String kk3 = String.valueOf(kk2);
          StringBuffer abuffer = new StringBuffer(kk3);
          // 倒叙排序
          String bbuffer = abuffer.reverse().toString();
          // 如果越界 返回0
          if(Long.valueOf(bbuffer)>Integer.MAX_VALUE){
              return 0;
          }else {
          // 如果不越界,判断是否是负数,是负数加上-,不是就直接返回
              return kk>0?Integer.valueOf(bbuffer):-Integer.valueOf(bbuffer);
          }
    }

但是具体看了性能描述和击败用户,证明这个解法相当不好

QQ截图20201223174920.png

题目优解

本题如果不考虑溢出问题,是非常简单的。解决溢出问题有两个思路:

  • 第一个思路是通过字符串转换加try catch的方式来解决,
  • 第二个思路就是通过数学计算来解决。
  • 由于字符串转换的效率较低且使用较多库函数,所以解题方案不考虑该方法,而是通过数学计算来解决。
  • 通过循环将数字x的每一位拆开,在计算新值时每一步都判断是否溢出。 溢出条件有两个,一个是大于整数最大值MAX_VALUE,另一个是小于整数最小值MIN_VALUE,设当前计算结果为ans,下一位为pop。
  • ans * 10 + pop > MAX_VALUE这个溢出条件来看
  • 当出现 ans > MAX_VALUE / 10 且 还有pop需要添加 时,则一定溢出
  • 当出现 ans == MAX_VALUE / 10 且 pop > 7 时,则一定溢出,7是2^31 - 1的个位数
  • ans * 10 + pop < MIN_VALUE这个溢出条件来看
  • 当出现 ans < MIN_VALUE / 10 且 还有pop需要添加 时,则一定溢出
  • 当出现 ans == MIN_VALUE / 10 且 pop < -8 时,则一定溢出,8是-2^31的个位数
  • Java整数类型Int:
    • int 数据类型是32位、有符号的以二进制补码表示的整数;
    • 最小值是 -2,147,483,648(-2^31)
    • 最大值是 2,147,483,647(2^31 - 1)
public static int reverse2(int x){
        int ans = 0;
        // 首先判断X不能为0
        while (x != 0){
            // pop为x求余数
            int pop = x % 10;
            // ans*10 要大于
            if (ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && pop > 7))
                return 0;
            if (ans < Integer.MIN_VALUE / 10 || (ans == Integer.MIN_VALUE / 10 && pop < -8))
                return 0;
            ans = ans * 10 + pop;
            x /= 10;
    }
    	return ans;
}

运行效果

效果展示.png

结束

​ 简单的一点点改动,效率提高了5倍


已有 0 条评论

    欢迎您,新朋友,感谢参与互动!