每日一个小算法之整数中每位上的数字进行反转 20190810

  • 作者: 凯哥Java
  • 算法刷题
  • 时间:2019-08-10 18:41
  • 1284人已阅读
简介 题目要求:给出一个32位的有符号整数,你需要将这个整数中每位上的数字进行反转。示例1:输入: 123输出: 321示例2:输入: -123输出: -321示例3:输入: 120输出: 21示例4:输入:9646324351输出: 0注意:假设我们的环境只能存储得下32位的有符号整数,则其数值范围为[−2的31次方, 2

题目要求:

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

示例 1:

输入: 123
输出: 321

示例 2:

输入: -123
输出: -321

示例 3:

输入: 120
输出: 21

示例 4:

输入:9646324351
输出: 0

注意:

假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−2的31次方,  2的31次方 − 1]。

请根据这个假设,如果反转后整数溢出那么就返回 0。

解决方案1:

最low的方法

思路:

转换成字符串。获取最后第一位和最后一位。用于判断是否是负数和是否是0

然后在进行判断,根据情况不同进行判断处理。

如下代码:

reverse(x) {
   String strX = Integer.(x).toString();
   [] charArr = strX.toCharArray();
   length = charArr.;
   String [] strArr = String [length];
   (i =;i<length;i++){
       strArr[i] = String.([]{charArr[i]});

   }
   String [] newStrArr =   String [length];
   String fasterStr =  strArr[];
   String lastStr = strArr[length-];
   index = ;
    (.equals(fasterStr)
            && .equals(lastStr)){
        newStrArr =   String [length-];
        newStrArr[] = fasterStr;
        (i= length-; i >;i--){
            index++;
            String str = strArr[i];
            newStrArr[index] = str;

        }
    }(.equals(lastStr)){
       newStrArr =   String [length-];
       (i= length-; i >=;i--){
           String str = strArr[i];
           newStrArr[index] = str;
           index++;
       }
   }(.equals(fasterStr)){
       newStrArr[] = fasterStr;
       (i= length-; i >;i--){
           index++;
           String str = strArr[i];
           newStrArr[index] = str;
       }
   }{
       (i= length-; i >=;i--){
           String str = strArr[i];
           newStrArr[index] = str;
           index++;
       }
   }


    String str = ;
    (i = ;i<newStrArr.;i++){
        str+= newStrArr[i];
    }
   {
       (!= str && != str){
           Integer ix = Integer.(str);
           x=ix.intValue();
       }
   }(Exception e){
        ;
   }

    .info(,x);
    x;
}

此方案运行结果:

d9408163065c98d8cc4d3c7ae3f89412.png

运行9毫秒,消耗内存35.4M

解决方案二:

从数学思维来处理的。

例如:1234 反过来就是4321

也就是个位和千百位互换、十位和百位互换。

这些明白了吧。也就是10的x方+Y%10.

其中x是位数。Y是数据。

看懂上面的,我们就能得到下面代码:

reverse2(x) {
    rpc = ;
    (x != )
    {
        newrpc = rpc*+ x%;
        .info(,(rpc*),x%,newrpc);
        ((newrpc - x%)/!= rpc){
            ;
        }
        rpc = newrpc;
        x = x/;
    }
    .info(,rpc);
    rpc;
}

运行后打印日志:

48d760b655b23feb21e12708f245d231.png

我们在来看看此方案执行结果:

f50e5b6d3281b93fe155ab4d0810a1a1.png

耗时3毫秒,内存消耗:34.3M

再来看第三种解决方案:

思路:使用字符串的反转方法。当溢出的时候异常直接返回0

reverse3(x) {
    {
        (x > ) {
            StringBuilder str = StringBuilder().append(x);
            Integer.(str.reverse().toString());
        }{
            StringBuilder str = StringBuilder().append(-x);
            Integer.(str.reverse().toString())*(-);
        }
    }(NumberFormatException e) {
        ;
    }
}

此方案运行结果:

ad5587252e5dbe9eddcbd10171ec92ff.png

方案4:

使用了math函数、位运算及字符串反转的

reverse4(x){
    start =  Math.(, ) - ;
    end = -Math.(, );
    (x<end && x>start){
        ;
    }
    df = Math.(x);
    Integer intDf = Math.(df);
    i = Math.(x);
    StringBuilder str = StringBuilder().append(i).reverse();
    {
        x = Integer.(str.toString());
    }(Exception e){
        ;
    }
    x*intDf ;
}

执行结果:

5351b47dace642b95038ec193eeaa4eb.png

方案五:

使用的是位移运输和math函数。

reverse5(x) {
    res = ;
    of = ((<< ) - ) / ;
    (x != ) {
        (Math.(res) > ((<< ) - ) / ){
            ;
        }
        res = res * + x % ;
        x /= ;
    }
    res;
}

执行结果:

5673ef717efb9785ec69636f10677df9.png

我们将5种方案进行对比:

0f23dd75a772f4b017fedbdf65dc79b4.png

发现第二种和第五种方案耗时最短。也就是使用数学思路和位移运行最快。

经过五中方案比较之后,我们是不是体会到:编程是一门艺术了。

本文出处:凯哥Java(kaigejava)

好了,今天小算法就到这里了。《每天一个小算法》希望直接可以坚持下去。


Top Top