LeetCode——回文数

NO.9 回文数简单

思路一：字符串法 最简单的解法就是直接将数字转换为字符串s，然后将字符串翻转得到re，最后判断s和rs是否相等，相等则是回文。

public boolean isPalindrome(int x) {
    String rs = new StringBuilder(x + "").reverse().toString();
    return (x+"").equals(rs);
}

思路二：翻转一半法 题目要求中有说，不能将整数转化为字符串来解决这个问题。但是依然可以使用字符串法的翻转思路，将数字进行翻转也并不难，例如“1221”，我们需要将后半部分“21”翻转为“12”再和前半部分“12”作比较，相同所以“1221”是回文数。

算法步骤：1.如果数字是负数，那么一定不是回文数。如果数字最后一位是”0“，但数字本身并不是”0“，那么该数字也一定不是回文数。2.如何翻转数字的后半部分：例如“x=1221”，先”1221%10“得到1，然后“x/=10”使x=122，最后”t=t*10+1”得到t=1；再次“122%10”得到2，然后“x/=10”使x=12，“最后”t=t*10+2”得到t=12。3.将数字后半部分翻转后得到的t和前半部分“12”进行比较，相等则为回文数。

如何判断翻转数字的位数已经到达原数字位数的一半？我们将原始数字除以 10，然后给反转后的数字乘上 10，所以，当原始数字小于反转后的数字时，就意味着我们已经处理了一半位数的数字。

参数数字x可能是偶数也可能是基数，如果x是偶数，例如“1221”，只要翻转后的“21”等于前半部分“12”，x就是回文数；如果x是基数，例如“12321”，后半部分翻转得到“123”，剩余的前半部分是”12“，但是原始数字中间的这个数字”3“并不影响回文（它总是与自身相等）,所以可以直接简单的将后半部分翻转得到“123”进行“123/10=12”的操作即可，然后再与前半部分进行比较。

public boolean isPalindrome(int x) {
//        两种不是回文数的特殊情况
        if (x<0||(x!=0&&x%10==0))return false;
//        后半部分翻转后的数字
        int reversedNumber=0;
        while (x>reversedNumber){
            reversedNumber=reversedNumber*10+x%10;
            x/=10;
        }
//        x可能是的位数可能是偶数或基数，如果是基数直接reversedNumber/10,简单的去掉中间的数
        return x==reversedNumber||x==reversedNumber/10;
    }

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.9 回文数 简单

NO.9 回文数简单