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?
法I：逐一比较最左端与最右端的数字
class Solution {
public boolean isPalindrome(int x) {
if(x<0) return false;
int left; //the first bit of the inteter
int right; //the last bit of the integer
int divisor = 1; //divisor of each iteration
int tmp = x;
//determine the initial value of divisor
while(x/divisor >= 10){
divisor *= 10;
}
//check palindrome
while(x>0){
left = x/divisor; //divided by divisor to get the first bit
right = x%10; //mod 10 to get the last bit
if(left != right) return false;
x = (x%divisor)/10; //mode divisor to remove the first bit, divided by 10 to remove the last bit
divisor /= 100;
}
return true;
}
}
数字问题注意：
1. 负数
2. 变换后 以0开始 （本题中，如10101）这种情况，除以divisor = 0，mod 10 = 最后那位。
有多少个0，就得经过多少次循环，才能使得divisor的长度和被除数相等。在长度不等的时候，没次都循环末尾需为0，才能符合Palindrome的判断。所以该算法仍然可以验证有0开头的情况。
法II：逆向思维，如果是parlindrome，那么求出的反转数应等于x
这个方法的优点：只遍历了整数长度的一半。
class Solution {
public boolean isPalindrome(int x) {
if(x<0 //negative number
|| (x%10 == 0 && x != 0)) //the check"x == reverseNum/10" has one exception: reverseNum is one-bit number but x isn't, this case only exist in x%10 == 0 && x != 0
return false;
int reverseNum = 0;
while(x > reverseNum){
reverseNum = reverseNum * 10 + x%10;
x /= 10;
}
if(x == reverseNum || x == reverseNum/10) return true; //check parlindrome of number with odd or even length
else return false;
}
}
parlindrome问题注意：
1. 数字长度单、双分开讨论。