题目描述
Determine whether an integer is a palindrome. Do this without extra space.
输入与输出
class Solution {
public:
bool isPalindrome(int x) {
}
};
题解与分析
解法一
首先注意一点，在本题中负数由于负号的原因不属于 Palindrome Number。然后可以使用与 7. Reverse Integer 类似的方法求出倒置的整数，比较即可。
C++ 代码如下：
class Solution {
public:
bool isPalindrome(int x) {
if (x == 0)
return true;
if (x < 0)
return false;
long long y = x, z = 0;
while (x != 0)
z = z * 10 + x % 10, x = x / 10;
return y == z;
}
};
该解法的时间复杂度为 O(n)。
解法二
在上一解法的基础上还可以做一些优化。
- 在开始时判断末位是否为 0，如果是 0 直接返回 false。
- 在 x <= z 时停止循环，如果原来的 x 是 Palindrome Number，那么有两种情况：
- 原来的 x 的长度是偶数，那么一定有 x == z。
- 原来的 x 的长度是奇数，那么一定有 x == z / 10。
- 如果原来的 x 不是 Palindrome Number，那么一定不满足上面两种情况。
C++ 代码如下：
class Solution {
public:
bool isPalindrome(int x) {
if (x == 0)
return true;
if (x < 0 || x % 10 == 0)
return false;
long long z = 0;
while (x > z)
z = z * 10 + x % 10, x = x / 10;
return x == z || x == (z / 10);
}
};
该解法的时间复杂度为 O(n)。
