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