9. 回文数
题目描述
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
示例1
输入: 121
输出: true
示例2
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例3
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:
你能不将整数转为字符串来解决这个问题吗?
首先有一些特殊情况我们可以直接判断不是回文数:
- 负数
- 大于 0 但末尾为 0
法一:
将数字转换成一个字符串,判断字符串是否是回文串即可。
法一代码:
class Solution {
public:
bool isPalindrome(int x) {
if ( x < 0 || x && x % 10 == 0 ) return false;
string s = to_string( x );
int i = 0, j = s.length() - 1;
while ( i < j ) {
if ( s[i] != s[j] ) return false;
++i, --j;
}
return true;
}
};
/*
时间:8ms,击败:91.97%
内存:6MB,击败:78.28%
*/
法二:
数学解法。
通过取整和取余操作来获取整数中对应的数字进行比较。
比如对于数字 2662:
- 计算 2662 / 1000 ,得到首位 2
- 计算 2662 % 1000,得到末位 2
- 继续比较 66
法二代码:
class Solution {
public:
bool isPalindrome(int x) {
if ( x < 0 || x && x % 10 == 0 ) return false;
int k = 1;
while ( x / k >= 10 ) k *= 10;
int l, r;
while ( x ) {
l = x / k;
r = x % 10;
if ( l != r ) return false;
x = ( x % k ) / 10;
k /= 100;
}
return true;
}
};
/*
时间:8ms,击败:91.97%
内存:6.2MB,击败:55.06%
*/
法三:
一个直观的解法:将整个数字逆序,然后判断是否相等即可。
但是逆序过程中可能会溢出,结果大于 INT_MAX
,所以此法不可行。
考虑到回文数的前半部分和后半部分相等,我们可以取出后半部分数字,然后判断是否相等(这里肯定不会出现溢出现象)。
注意,数字的长度可能为奇数或者偶数,需要特殊处理一下。
法三代码:
class Solution {
public:
bool isPalindrome(int x) {
if ( x < 0 || x && x % 10 == 0 ) return false;
if ( x < 10 ) return true;
int ret = 0;
while ( ret <= x ) {
ret = ret * 10 + x % 10;
x /= 10;
if ( ret == x || ret == x / 10 ) return true;
}
return false;
}
};
/*
时间:4ms,击败:98.64%
内存:6.2MB,击败:36.46%
*/