2014
11-19

# LeetCode-Palindrome Number[模拟]

### Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

//LeetCode, Palindrome Number
// 时间复杂度O(1)，空间复杂度O(1)
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) return false;
int d = 1; // divisor
while (x / d >= 10) d *= 10;

while (x > 0) {
int q = x / d;  // quotient
int r = x % 10;   // remainder
if (q != r) return false;
x = x % d / 10;
d /= 100;
}
return true;
}
};


Java代码:

public class Solution {
public boolean isPalindrome(int x) {
if(x < 0) return false;
int reverseX = 0;
int tmp = x;
while(tmp != 0){
reverseX = reverseX * 10 + tmp % 10;
tmp /= 10;
}
return reverseX == x;
}
}

1. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。

2. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

3. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？