方法一:反转一半数字
考虑特殊情况:
- 负数不是回文数,如-123,反过来为321-。
- 个位数为0的非0数不是回文数,比如120,反过来为021。
对于一般情况,我们只需要取出后半段反转再跟前半段比较即可。如:
- 12321,后半段321反转为123,前半段12,是回文数。
- 1221,后半段21反转为12,前半段12,是回文数。
- 12324,后半段324反转为423,前半段12,不是回文数。
- 1223,后半段23反转为32,前半段12,不是回文数。
为什么不是直接反转整体呢?因为反转后的数据有可能超出INT_MAX,导致溢出。
注意到整数操作的3个技巧:
- xmod10可以取出x的最低位。如x=123,xmod10=3。
- x=x*10+y,
,可以在x后面续上y。如x=123,y=4,那么经过这个操作后x=1234。
- x/=10可以去掉x的最低位。如x=123,x/=10,x=12。
如何反转呢?取r=0,每次用技巧1取出x的最低位,再用技巧2续到r上,最后用技巧3去掉x的最低位。如:
- x=12321,r=0→x=1232,r=1→x=123,r=12→x=12,r=123。
- x=1221,r=0→x=122,r=1→x=12,r=12。
什么时候才处理完一半的位数呢?显然,r的位数越来越大,x的位数越来越小,当r的位数≥x的位数时,即r≥x时就处理完了。偶数位的回文数处理到最后满足x==r(参考一般情况的案例1),奇数位的回文数处理到最后满足x==r/10(参考一般情况的案例2)。如果不满足x==r或x==r/10,则不是回文数。
// 方法一:反转一半数字
class Solution {
public:
bool isPalindrome(int x) {
// 负数、个位数为0的非0数
if (x < 0 || (x % 10 == 0 && x != 0))
return false;
// 反转后半段
// r越来越大,x越来越小
// 当r的位数比x大(或相等)则处理完一半的位数
int r = 0;
while (r < x)
{
r = r * 10 + x % 10;
x /= 10;
}
// 偶数位 奇数位
return r == x || r / 10 == x;
}
};
方法二:字符串
我们也可以先把整数转换为字符串,再判断字符串是否为回文串。
整数转换为字符串可以使用整数处理技巧2和3,每次取出最低位插入到字符串中,这样转换出来的字符串和原来的整数是反过来的,如123转换为字符串后就变成了"321",但是是否回文的性质不变。
判断回文串的思路是:取2个指针指向最左边和最右边的字符,从2边向中间移动,判断沿途的字符是否相同,如果都相同就是回文串。
// 方法二:字符串
class Solution {
public:
bool isPalindrome(int x) {
// 负数和个位数为0的非0数
if (x < 0 || (x % 10 == 0 && x != 0))
return false;
//string s = to_string(x);
// 取出每一位插入,这样的字符串是反的
string s;
while (x)
{
s += (x % 10 + '0');
x /= 10;
}
// 判断s是否为回文串
int left = 0;
int right = s.size() - 1;
while (left < right)
{
if (s[left] != s[right])
return false;
++left;
--right;
}
return true;
}
};