文章目录

• 9. 回文数
• • 题目描述
  • 解题思路
  • 代码实现
• 906. 超级回文数
• • 题目描述
  • 解题思路
  • 代码实现

9. 回文数

题目描述

解题思路

• 首先将整数x转换为字符串型x_str；
• 遍历x_str.length()/2次，比较第 i 位与倒数第 i 位字符是否相同，如果不同返回false；
• 遍历结束，返回true。

代码实现

class Solution {    public boolean isPalindrome(int x) { if(x<0){ //x为负肯定不是回文数     return false; } if(x<10){// x为个位数一定是回文数     return true; } String x_str = Integer.toString(x);     //将x装换位字符串 int length = x_str.length(); for(int i=0;i<length/2;i++){     if(x_str.charAt(i) != x_str.charAt(length-i-1)){    //比较第i位与倒数第i为是否相同  return false;     } } return true;    }}

906. 超级回文数

题目描述

解题思路

理清思路：

1. 题目中给定数字x范围为1~10¹⁸，并要求x为回文数并且（&&）x² 要为回文数，则我们可以先判断x是否为回文数，当x是回文数时再来判断x²是否为回文数。这样我们就把遍历范围缩小到了1~10⁹；
2. 在1~10⁹ 中，如果x为回文数，必须满足前一半数字与后一半数字为逆序数。那么后一半的数字就可以由前一半的数字逆序遍历得到，我们可以把x转换为字符串型，逆序遍历前一半的字符，并拼接到前一半字符的后面。这样我们就又可以把遍历范围缩小到了1~10⁵；
3. 在拼接的时候存在两种情况：
   （1）当逆序数的数位为奇数时，例如：1234321，它由1234拼接得到，拼接过程如下：初始为1234，逆序遍历1234的前n-1位，即 1234 + ‘3’ + ‘2’ + ‘1’ ==> 1234321。
   （2）当逆序数的数位为偶数时，例如：12344321，它也由1234拼接得到，拼接过程如下：初始为1234，逆序遍历1234的每一位，即 1234 + ‘4’ + ‘3’ + ‘2’ + ‘1’ ==> 12344321。
   综上，当位数为奇数的时候，从从倒数第二位向前遍历拼接；当位数为偶数的时候，从最后一位向前遍历拼接。

通过以上分析我们把遍历范围缩小到了1~10⁵ ，我们只需要遍历1~10⁵ 内的所有数字，并按上述两种方式拼接得到一个新的数字，判断新的数字是否回文数即可。

结合下面代码会更清晰：

代码实现

class Solution {    public int superpalindromesInRange(String left, String right) { long left_long = Long.valueOf(left); long right_long = Long.valueOf(right); int count=0; int MAX = 100000; //统计奇数拼接得到的回文数 for(int i=1;i<MAX;i++){     StringBuilder sb = new StringBuilder(Integer.toString(i));     for(int j=sb.length()-2;j>=0;--j){//奇数拼接，从倒数第二位向前遍历拼接  sb.append(sb.charAt(j));     }     long sb_long = Long.valueOf(sb.toString());     sb_long *=sb_long;     if(sb_long>right_long){//超过给定的范围  break;     }     if(sb_long>=left_long && isPalindrome(sb_long)){//在范围内，并且平方为回文数  ++count;     } }//统计偶数拼接得到的回文数 for(int i=1;i<MAX;i++){     StringBuilder sb = new StringBuilder(Integer.toString(i));     for(int j=sb.length()-1;j>=0;--j){//偶数拼接，从最后一位向前遍历拼接  sb.append(sb.charAt(j));     }     long sb_long = Long.valueOf(sb.toString());     sb_long*=sb_long;     if(sb_long>right_long){//超过给定的范围  break;     }     if(sb_long>=left_long && isPalindrome(sb_long)){//在范围内，并且平方为回文数  ++count;     } } return count;    }//判断x是否为回文数    public boolean isPalindrome(long x) { if(x<0){ //x为负肯定不是回文数     return false; } if(x<10){// x为个位数一定是回文数     return true; } String x_str = Long.toString(x);     //将x装换位字符串 int length = x_str.length(); for(int i=0;i<=length/2;i++){     if(x_str.charAt(i) != x_str.charAt(length-i-1)){    //比较第i位与倒数第i为是否相同  return false;     } } return true;    }}