题目等级: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)