LeetCode NO. 9 Palindrome Number
LeetCode 第9題 回文數(shù)
DIFFICULTY（難度）
EASY
容易
DESCRIPTION（題面）
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
判斷一個整數(shù)是否是回文數(shù)，回文數(shù)就是正讀反讀都相同的數(shù)字
EXAMPLE（樣例）
ONE
Input: 121（輸入：121）
Output: true（輸出：true）
輸入：121
輸出：true
TWO
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.
輸入：-121
輸出：false
解釋：從左向右讀是-121，從右向左讀是121-避乏，因此不是回文數(shù)
THREE
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
輸入：10
輸出：false
解釋：從右向左讀為01憾儒，因此10不是回文數(shù)友扰。
FOLLOW UP
Could you solve it without converting the integer to a string?
你能否在不將整數(shù)轉(zhuǎn)化為字符串的情況下蔬芥，判斷出該整數(shù)是不是回文數(shù)？
SOLUTION（解題）
class Solution {
public:
bool isPalindrome(int x) {
if(0 > x || (x % 10 == 0 && x != 0)) {
return false;
}
int reversed = 0;
while(x > reversed) {
reversed = reversed * 10 + x % 10;
x = x / 10;
}
return x == reversed || x == reversed/10;
}
};
NOTE（注）
思路1：轉(zhuǎn)字符串
將整形轉(zhuǎn)換成字符串漆改，從兩側(cè)向內(nèi)依次比較即可沾瓦。既然題目提示了不轉(zhuǎn)換字符串的方式判斷满着，何不試一下？
思路2：反轉(zhuǎn)整個數(shù)字
將整個整數(shù)反過來贯莺，如果反轉(zhuǎn)數(shù)字和原數(shù)字相同那就說明這個整數(shù)是回文數(shù)风喇，第一次提交就是這種方案，結(jié)果遇到了reversed越界缕探，因為使用了乘法嘛魂莫，越界沒有考慮到，改成long類型通過爹耗。提交后查看最佳提交的解題思路耙考，如思路3
思路3：反轉(zhuǎn)數(shù)字的一半
既然會有越界問題，那不計算那么多位就好了潭兽，也就是不要把整個數(shù)字都反轉(zhuǎn)過來倦始。從思路2的計算過程，原數(shù)字x在不斷被除10山卦，而余數(shù)則是不斷的被累加到反轉(zhuǎn)數(shù)的低位鞋邑，那是不是說如果這個數(shù)字是回文數(shù)，那么當(dāng)計算到一半的時候怒坯，原數(shù)字x會與反轉(zhuǎn)數(shù)reverse是相等的炫狱，所以只要反轉(zhuǎn)一半就好了，那如何判斷反轉(zhuǎn)到一半的位置了呢剔猿，因為x在不斷被除10，reverse不斷在低位累加嬉荆，那么當(dāng)x小于reverse的時候归敬，就說明已經(jīng)轉(zhuǎn)換了一半的數(shù)字了。
例1：101
計算過程變量值
| x | reversed |
|---|---|
| 101 | 0 |
| 10 | 1 |
| 1 | 10 |
發(fā)現(xiàn)reverse的值其實是比x的最終值要大的，發(fā)現(xiàn)reverse的最后一位汪茧，就是原x中間的那一位椅亚，而這一位并不影響判斷這個數(shù)是不是回文數(shù)，所有的奇數(shù)位數(shù)的整數(shù)都符合這個規(guī)律舱污，所以只要判斷去掉個位的其余數(shù)字相同即可呀舔，因此判斷條件是 x == reversed/10，如例2
例2： 10101
計算過程變量值
| x | reversed |
|---|---|
| 10101 | 0 |
| 1010 | 1 |
| 101 | 10 |
| 10 | 101 |
例3：1001
計算過程變量值
| x | reversed |
|---|---|
| 1001 | 0 |
| 100 | 1 |
| 10 | 10 |
