LeetCode NO. 9 Palindrome Number
LeetCode 第9题 回文数
DIFFICULTY（难度）
EASY
容易
DESCRIPTION（题面）
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
判断一个整数是否是回文数，回文数就是正读反读都相同的数字
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-，因此不是回文数
THREE
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
输入：10
输出：false
解释：从右向左读为01，因此10不是回文数。
FOLLOW UP
Could you solve it without converting the integer to a string?
你能否在不将整数转化为字符串的情况下，判断出该整数是不是回文数？
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：转字符串
将整形转换成字符串，从两侧向内依次比较即可。既然题目提示了不转换字符串的方式判断，何不试一下？
思路2：反转整个数字
将整个整数反过来，如果反转数字和原数字相同那就说明这个整数是回文数，第一次提交就是这种方案，结果遇到了reversed越界，因为使用了乘法嘛，越界没有考虑到，改成long类型通过。提交后查看最佳提交的解题思路，如思路3
思路3：反转数字的一半
既然会有越界问题，那不计算那么多位就好了，也就是不要把整个数字都反转过来。从思路2的计算过程，原数字x在不断被除10，而余数则是不断的被累加到反转数的低位，那是不是说如果这个数字是回文数，那么当计算到一半的时候，原数字x会与反转数reverse是相等的，所以只要反转一半就好了，那如何判断反转到一半的位置了呢，因为x在不断被除10，reverse不断在低位累加，那么当x小于reverse的时候，就说明已经转换了一半的数字了。
例1：101
计算过程变量值
| x | reversed |
|---|---|
| 101 | 0 |
| 10 | 1 |
| 1 | 10 |
发现reverse的值其实是比x的最终值要大的，发现reverse的最后一位，就是原x中间的那一位，而这一位并不影响判断这个数是不是回文数，所有的奇数位数的整数都符合这个规律，所以只要判断去掉个位的其余数字相同即可，因此判断条件是 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 |
