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?
这一题很有意思，要我们判断一个整数是否是回文数。 首先负数不是回文数，个位数是回文数。但是怎样判断大于9的整数是否是回文数呢？ 首先想到的是把int转换为string表示，这样就很方便判断了，但是题目要求不能用额外的存储空间，也就是不能用和x位数线性以上的存储空间，当然几个常数空间是可以的。 后来想依次取出数字的首尾数字，判断是否相等。但是中间有0出现时会有问题，比如1000021，去掉首尾1之后只剩int x=2了，导致判断错误。 还有一个办法是将x转换为x的逆序x’，然后依次判断x和x’的末尾是否相等，但是x’可能超出int表示范围，又作罢。 后来观察发现，回文数字765567在转换为逆序数的过程中，肯定有某个状态，x==x’，比如765=765，而这时x’肯定不会超出int的表示范围。所以我们可以在边逆序的时候边判断。 完整代码如下：
class Solution {
public:
bool isPalindrome(int x)
{
if (x < 10)
return x >= 0;
if (x % 10 == 0)
return false;
int y = 0;
while (x > y) {
y = y * 10 + x % 10;
if (x == y) //76567
return true;
x /= 10;
if (x == y) //765567
return true;
}
return false;
}
};本代码提交AC，用时76MS。
二刷。常规解法，取出每一位数字进行判断：
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0) return false;
if(x == 0) return true;
if(x % 10 == 0) return false;
vector<int> digits;
while(x != 0) {
digits.push_back(x % 10);
x /= 10;
}
int l = 0, r = digits.size() - 1;
while(l < r) {
if(digits[l] != digits[r]) return false;
++l;
--r;
}
return true;
}
};本代码提交AC，用时52MS。