经典算法（二）之回文数

回文数

首先，不知道什么是回文的，请看我的另一篇文章，回文http://blog.csdn.net/u010042858/article/details/71156352

接下来给大家讲讲回文数，也就是判断一个数是不是回文，我们之前说的

回文都是字符串，是数字又该怎么处理，我们这里只是判断整数是不

是回文，如果是负数，那么前面有符号存在，结果还是判断后面的数字，

所以负数暂时不考虑，思路一样，我们只是判断一个自然数就行，可以借

鉴来判断其他类型的。

在解决是否回文的问题之前，我们先解决一个问题，如何将整型反转？

一、Integer反转

package com.zl; import java.util.Scanner; /** * 求数字反转算法 * * @author zl * @time 2017.05.03 */ public class ReverseInteger { private static int answer1, answer2; public static void main(String[] args) { System.out.println("请输入数字："); Scanner sc = new Scanner(System.in); int num = sc.nextInt(); answer1 = reverse1(num);//solution1 answer2 = reverse2(num);//solution2 System.out.println("solution1 反转后为：" + answer1); System.out.println("solution2 反转后为：" + answer2); } /** * solution1 * 思路： * 例如：求 123 的 反转，反转后为 321 * 1.取所给数的最后一位 3 ，也就是取余，123=3，去掉3以后变为 123/10=12 * 2.每次都取最后一位数，拼接到结果后面，即 3*10+2=32，最后就是32*10+1=321 * * 12345的反转是54321 * 5*10+4=54 , 54*10+3=543, 543*10+2=5432 , 5432*10+1=54321 * */ private static int reverse1(int num) { int result = 0; while (num != 0) { //若为0，取反则为0，直接返回result = 0 int tail = num % 10; //每次取最后一位，求余数 int newResult = result * 10 + tail; //之前的结果乘以10，加上新取得的数，就是最新的结果 if ((newResult - tail) / 10 != result) { //判断是否越界，整型的范围在-2^31~2^31-1,超出范围则返回0 //如果越界，将上一步newResult = result * 10 + tail，转换之后结果会不相等 return 0; } result = newResult; num = num / 10; //每次去掉最后一位 } return result; } //solution2，和solution1类似，主要是判断越界不一样 private static int reverse2(int num) { long result = 0; while (num != 0) { result = result * 10 + num % 10; num = num / 10; if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) { //判断越界 return 0; } } return (int) result; } }

结果为：

请输入数字： 12345 solution1 反转后为：54321 solution2 反转后为：54321

二、回文数

在取反的基础上，判断是否回文数就很简单了。

package com.zl; import java.util.Scanner; /** * 判断是否回文数算法 * * @author zl * @time 2017.05.04 */ public class PalindromeNumber { private static boolean answer; public static void main(String[] args) { System.out.println("请输入数字："); Scanner sc = new Scanner(System.in); int num = sc.nextInt(); answer = isPalindrome(num); System.out.println("是否为回文：" + answer); } private static boolean isPalindrome(int num) { if (num < 0 || (num != 0 && num % 10 == 0)) { //负数因为符号的原因，严格来说不算回文，所以排除，如果最后一位是0，回文要0开头，就不是数，故返回false return false; } int sum = 0; while (num > sum) { //回文只需要取一半就可以判断 sum = sum * 10 + num % 10; //数的取反 num = num / 10; } return (num == sum) || (num == sum / 10); //例如，输入1234321，则num=123，sum=1234，结果为true //或者123321，num=123,sum=123,故使用(num == sum) || (num == sum / 10)判断 } }

结果如下：

请输入数字： 1234321 是否为回文：true

请输入数字： 123321 是否为回文：true

请输入数字： 12345 是否为回文：false

---

每天一个算法，提高自己

---