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~1018，并要求x为回文数并且（&&）x2 要为回文数，则我们可以先判断x是否为回文数，当x是回文数时再来判断x2是否为回文数。这样我们就把遍历范围缩小到了1~109；
2. 在1~109 中，如果x为回文数，必须满足前一半数字与后一半数字为逆序数。那么后一半的数字就可以由前一半的数字逆序遍历得到，我们可以把x转换为字符串型，逆序遍历前一半的字符，并拼接到前一半字符的后面。这样我们就又可以把遍历范围缩小到了1~105；
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~105 **，我们只需要遍历1~105 内的所有数字，并按上述两种方式拼接得到一个新的数字，判断新的数字是否回文数即可。

结合下面代码会更清晰：

代码实现

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;
    }
}

创作挑战赛

新人创作奖励来咯，坚持创作打卡瓜分现金大奖