題目
Determine whether an integer is a palindrome. Do this without extra space.
Some hints:
Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.
解題思路:
這道題首先要理解什么是回文數(shù)字干发,就是從左到右的數(shù)字順序和從右到左的數(shù)字順序是一樣的菩收,比如 12321客冈。判斷一個(gè)數(shù)字是否是回文數(shù)字有以下規(guī)則
- 負(fù)數(shù)不是回文數(shù)字。
- 能被 10 整除的也不是負(fù)數(shù)趣惠,0 除外罚斗。
- 若是數(shù)字的位數(shù)是偶數(shù)位 n眉撵,那么從右向左反轉(zhuǎn) n/2 位數(shù)字空繁,然后和剩下的 n/2 位從左向右數(shù)字比較,若是相等則是回文數(shù)字圾叼。 如
12344321 可以拆解成 1234 和 1234 對(duì)比蛤克。 - 若是數(shù)字的位數(shù)是奇數(shù)位 n+1 ,那么從右向左反轉(zhuǎn) n/2 + 1 位數(shù)字得到數(shù)字 m,再將 m / 10 去掉個(gè)位數(shù)的到 q 夷蚊,然后和剩下的 n/2 位從左向右數(shù)字比較构挤,若是相等則是回文數(shù)字。如 12321惕鼓,可以拆解成 12 和 12 對(duì)比筋现。
解題代碼:
class Solution {
public:
bool isPalindrome(int x) {
// 去掉負(fù)數(shù)和能夠被 10 整除的數(shù),0 除外
if(x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
// 反轉(zhuǎn)數(shù)字
int revertedNumber = 0;
while(x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
return x == revertedNumber || x == revertedNumber/10;
}
};