1. 题目地址

2. 题目描述

英文描述

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.

Example 1:
Input: x = 121
Output: true

Example 2:
Input: x = -121
Output: false

Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:
Input: x = 10
Output: false

Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Example 4:
Input: x = -101
Output: false

Constraints:
-2^31 <= x <= 2^31 - 1
 
Follow up: Could you solve it without converting the integer to a string?

中文描述

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

示例 1：
输入：x = 121
输出：true

示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

示例 4：
输入：x = -101
输出：false

提示：
-2^31 <= x <= 2^31 - 1

3. 解题思路

直接的想法是转化为字符串：首先想到的就是将数字转为字符串，通过判断字符串是否是回文串来解决。
进一步的，可以利用数字的特性来解决，判断的是回文数不是回文串
字符串方法1：直接s[::-1]==s判断：
- 思想：首先，将数字转换为字符串，s=str(x)；然后，return s[::-1]==s。
- 分析：但是这种方法需要额外的非常量空间来创建字符串。
- 时间复杂度：
- 空间复杂度：
字符串方法2：用快慢指针来判断：
- 思想：
  （1）采用双指针：个头指针，一个尾指针，分别指向字符串的头和尾。
  （2）若两个指针上的元素不相同，则直接返回False，结束判断。
  （3）若两个指针上的元素相同，则头指针向后一步，尾指针向前进一步，头尾指针同时更新，直到头尾指针相遇，返回True；或者所指的元素出现不相同的情况，返回False。
- 分析：但是这种方法需要额外的非常量空间来创建字符串。
- 时间复杂度：O(log n)
- 空间复杂度：O(log n)
数字特性方法1：将数字本身反转，然后将反转后的数字与原始数字进行比较：
- 思想：按照数字特性对数字本身进行反转，得到完全反转后的数字后，与原始数字进行比较，如果相等就是回文数。
- 问题：如果反转后的数字大于 int.MAX，会遇到整数溢出的问题，会报错。

反转数字的过程说明：

（1）以数字2662来说，原始数字num=2662，设置处理后的原始数字初始值为cur=2662，初始反转后的数字reverse=0。
（2）每次迭代进行的步骤都是：
     reverse=reverse*10+cur%10，cur=cur/10。
（3）详细解释（可跳过不看）：
     第一步：得到最后一位数字2662%10=2，此时原始数字需要变为2662/10=266，方便得到倒数第二位数字。
            此时：reverse = 0*10 + 2662%10 = 0+2 = 2，
                     cur = 2662/10 = 266。 
     第二步：得到倒数第二位数字266%10=6，此时原始数字变为266/10=26。
            此时：reverse = 2*10 + 266%10 = 20 + 6 = 26，
                     cur = 266/10 = 26。 
     第三步：得到倒数第三位数字26%10=6，此时原始数字变为26/10=2。
            此时：reverse = 26*10 + 26%10 = 260 + 6 = 266，
                     cur = 26/10 = 2。
     第四步：得到倒数第四位数字2%10=2，此时原始数字变为2/10=0。
            此时：reverse = 266*10 + 2%10 = 2660 + 2 = 2662，
                     cur = 2/10 = 0。
     第五步：反转后的数字reverse=2662，原始数字num=2662，两者相等，该数为回文数。

数字特性方法2：反转数字的一半，并与另一半做比较：
- 思想：为了避免数字反转可能导致的溢出问题，只反转int 数字的一半。如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。
- 分析：以数字2662举例，如果只反转后半部分的数字，62反转后就是26，与前半部分数字相同，则可以判断该数字是回文数。
  
  （1）第一步，首先用2662%10=2，可以得到最后一位数字是2；为了得到倒数第二位数字，原始数字就需要变为2662/10=266。此时，反转后的数字是2。
  
  （2）第二步，原始数字266%10=6，得到倒数第二位数字是6；处理后的原始数字变为266/10=26。此时，反转后的数字是2*10+6=26。
  
  （3）迭代结束的判断条件是：迭代已经过半或者正好对半，也就是已经过了数字的一半了。
  
  （4）迭代过半的条件是：反转后的数字>=处理后的原始数字。
  ??（如果还没过半，原始数字肯定比反转后的数字的位数要多，那肯定原始数字更大，如果发现原始数字比反转后的数字小，或者相等，就说明迭代已经过半了。）
  
  （4）偶数位的数字2662：反转后半部分的数字，62反转后就是26。
  ???反转后的数字26=前半部分数字26，迭代结束；
  ???反转后的数字=前半部分数字，则可以判断该数字是回文数。
  
  （5）奇数位的数字26562：反转后半部分的数字得到26，接着迭代得到反转数字265。
  ???反转后的数字265>前半部分数字26，迭代结束。
  ???由于5是中间位，总是与自己相等，反转后也是它本身，可以整除10去掉不做考虑。所以，如果反转后的数字265/10=处理后的原始数字26，就可以判断出是回文串了。
  ???因此，如果奇数位的数字迭代结束时：
  ???反转后的数字/10=前半部分数字，就说明该数字是回文数。
- 时间复杂度：O(log n)，对于每次迭代，都是用输入除以 10，因此时间复杂度为 O(log n)。
- 空间复杂度：O(1)。常数空间存放变量。

反转一半数字的过程总结：

（1）初始前半部分数字cur = 原始数字num，初始反转后的数字reverse = 0。
（2）每次迭代，进行取余操作（%10），取出最后一位数字：cur % 10。
（2）得到反转后的数字：reverse = reverse * 10 + cur % 10。
（3）每次迭代，剩余的前半部分数字变为：cur = cur / 10。
（4）判断迭代是否结束：cur <= reverse，说明数字已经过半或者正好对半。
（5）判断是否是回文数：考虑奇数位数字和偶数位数字。
    如果是偶数位数字的回文数，reverse = cur；
    如果是奇数位数字的回文数，reverse/10 = cur。