【LeetCode】9、Palindrome Number(回文数)

题目等级:Easy

题目描述:

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

  题意:判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。


解题思路:

  本题比较简单,一个很直观的做法是我们很熟悉回文字符串的判断,因此可以将整数转为字符串,从而利用回文字符串的判断来判断回文数。当然,题目也提示我们能不能采用别的办法。

  解法一:整数反转后比较

  整数反转后如果和原来的数相同,那么它就一定是回文数,而如何反转一个整数,在上一题中已经解决,可以参考:【LeetCode】7、Reverse Integer(整数反转)

  解法二:只反转一半

  实际上,从解法一也可以看出,么有必要都进行反转,只需要反转整数的后一半,与前一半进行比较即可。

  这里主要需要注意的问题有三个:一是如何判断已经反转了一半,判断条件是:剩下的数字小于已经反转完成的数字。二是需要判断奇数位和偶数位不同的情况,若一共有奇数位,那么反转之后比前一半多一位,需要%10,若一共是奇数位,那么说明反转的后一半与前一半位数相同。三是注意特殊情况:负数都不可能是回文数,最后一位如果是0的数,除0之外的数也不可能是回文数。

class Solution {
    public boolean isPalindrome(int x) {
        //将后一半反转,与前一半比较
        //重点:如何知道我们已经反转到了一半,剩下的数字小于已经反转完成的数字
        if(x<0 || (x%10==0 && x!=0)) //负数都不可能是回文数,最后一位是0的除0之外都不可能是回文数
           return false;
        int reverse=0;
        while(x>reverse){
            reverse=reverse*10+x%10;
            x=x/10;
        }
        if(x==reverse||x==reverse/10)
            return true;
        return false;
    }
}

  时间复杂度:有多少位就循环多少次的一半,所以是1/2 * lg(n),即以10为底,时间复杂度O(lgn)

  空间复杂度:O(1)

上一篇:LeetCode 131. 分割回文串(Palindrome Partitioning)


下一篇:Check Number is Palindrome or Not C++