题目描述
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例：
输入: 121
输出: true
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
题目链接： https://leetcode-cn.com/problems/palindrome-number/
思路1
将数字转为字符串，然后使用两个指针left和right，left从前往后遍历，right从后往前遍历。判断left和right两个位置的字符串是否相等，如果有不等的，返回false. 代码如下：
class Solution {
public:
bool isPalindrome(int x) {
string s = to_string(x);
int left=0, right=s.length()-1;
while(left<right){
if(s[left]!=s[right]){
return false;
}
left++;
right--;
}
return true;
}
};
- 时间复杂度：O(n)
n为字符串长度。 - 空间复杂度：O(n)
思路2
如果不能转为字符串，则可以数字拆分到数组里面，然后使用同样的两个指针来判断。代码如下：
class Solution {
public:
bool isPalindrome(int x) {
vector<char> v;
bool isNegative = false;
if(x<0) isNegative = true;
while(x!=0){
v.push_back(char(x%10));
x /= 10;
}
if(isNegative) v.push_back('-');
int left=0, right=v.size()-1;
while(left<right){
if(v[left]!=v[right]){
return false;
}
left++;;
right--;
}
return true;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)
思路3
如果一个数是回文数，则该数的前半部分等于后半部分，如1221,12321。所以我们可以先计算该数的后半部分，然后与前半部分进行比较。代码如下：
class Solution {
public:
bool isPalindrome(int x) {
if(x<0 || (x%10==0 && x!=0)) return false;
int reversedNum = 0;
while(x>reversedNum){ // 注意条件
reversedNum = reversedNum*10 + x%10;
x /= 10;
}
return x==reversedNum || x==reversedNum/10; // 注意返回值是两部分
}
};
因为负数不可能是回文数，而且末尾是0的数不可能是回文数（除0外），所以遇到这两种情况可以直接返回false。
在循环过程中，通过条件 x>reversedNum 来判断reversedNum是否代表后半部分。
在返回的结果中除了判断 x==reversedNum 外（x是偶数的情况下），还要判断 x==reversedNum/10（x是奇数的情况下）。
- 时间复杂度：O(n)
- 空间复杂度：O(1)