每日一个小算法之回文数这么玩20190811

判断是不是回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
示例 4:
输入: 0
输出: true
解释: 从右向左读, 为 0 。因此它是一个回文数。
方案一：
使用stringBuffer的reverse函数。
思路：
需要将输入的整数转stringbuffer之后，使用stringBuffer的reverse函数反转之后。记住str2.然后str1和str2进行比较。如果相等说明是回文数。
需要注意,特殊情况
数据为0的时候，数据为负数。
具体代码：

/**

    * 使用字符串的

    * @param x

    * @return

    */

   public boolean isPalindrome(int x) {

       if(x<0){

           return false;

       }

       StringBuffer sb = new StringBuffer().append(x);

       StringBuffer sb2 = new StringBuffer().append(x);

       //反转后的

       String reSb = sb.reverse().toString();

       if(reSb.startsWith("0")&&reSb.length()>1){

           return false;

       }

       if(sb2.toString().equals(reSb.toString())){

           return true;

       }

       return  false;

   }

 

运行结果：

执行耗时：223毫秒。消耗内存51.1M
再来看看第二种解决方案。
思路：从数学角度出发的。
我们知道，数学学科都是十进制的。我们就利用这一特性来进行处理。
假设数据是123
当一个数除以10就是取整。123/10=12
当一个数模10得到的就是余数。123%10 = 3
根据这特性，我们就可以得到如下代码：

 

 /**

    * 从数学角度出发

    * @param x

    * @return

    */

   public boolean isPalindromeMath(int x) {

       if(x<0){

           return false;

       }

       int current = 0;

       int newx = x;

       while (newx!=0){

           current = current*10+newx%10;

           newx=newx/10;

           System.out.println(current +":"+newx);

       }

 

       if(current==x){

           return true;

       }

       return  false;

   }

我们先来看看，current及newx在每次循环的值：

这样就更容易看出取模、取整的数据了。
我们来看看使用数学算法执行的结果：

耗时：14毫秒。内存消耗37.9M.
是不是比使用字符串来说，执行时间快了很多。
我们在来看看第三种方案：
这一种是巧妙的。感觉这一种方案很有意思。
我们先来看看：
121、1221
来找规律。正着看，反着看都是一样的。所以呢，我们可以只关心前一般。
比如121的前一半就是：1
1221的前一半就是：12
是不是发现规律了。
我们只需要将前一半反转之后和后一半进行比较。如果相等就是回文数了。
这里需要注意的是特殊情况：负数、0。
这里就写个麻烦的举例：

/**

    * 只反转一半.

    * @param x

    * @return

    */

   public boolean isPalindromeLess(int x) {

       if(x<0){

           return false;

       }

       StringBuffer sb = new StringBuffer().append(x);

       int xlength = sb.toString().length();

       if(xlength==1){

           return true;

       }

       String startStr = "";

       String endStr = "";

       startStr = sb.toString().substring(0,xlength/2);

       endStr =  sb.toString().substring(xlength/2,xlength);

       if(xlength%2!=0){

           if(xlength==2){

               endStr =  sb.toString().substring(xlength/2,xlength);

           }else{

               endStr =  sb.toString().substring(xlength/2+1,xlength);

           }

 

       }

 

       StringBuffer startStrSb = new StringBuffer().append(startStr).reverse();

       System.out.println(startStrSb+":"+endStr);

 

       if(startStrSb.toString().equals(endStr)){

           return true;

       }

 

       return  false;

   }

 

这种方案是不是很巧妙？
使用第二种及其简单的：

代码这里就不贴了。同步到git上面了。欢迎大家下载查看。