一、题目
1、算法题目
“判断给定的整数是否是一个回文数。”
题目链接： 来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/pa…
2、题目描述
给你一个整数 x ，如果 x 是一个会问整数，返回 true；否则，返回 false。
回文数是指正序（从左到右）和倒序（从右到左）读都是一个整数。例如，121 是回文，而 123 不是。
比如：
输入：x = 121
输出：true
输入：s = "-121"
输出：false
解析：从左向右读-121,从右向左读123-，并不是一个回文数。
二、解题
1、思路分析
这道题第一个想法是将数字转换成字符串，然后检查字符串是否为回文，但是这个需要额外的空间来创建字符串。
第二个想法是直接将数字本身反转，然后将反转后的数字与原始数字进行比较，如果相同，那么这个整数就是回文。
但是，可能会出现反转后的数字大于INT.MAX的情况，也就是整数溢出。
那么按照第二个想法，为了避免整数溢出问题，可以考虑只反转数字的一半，例如，1221，将数字12反转为21，与后半部分21比较，因为二者相同，所以数字1221是回文。
2、代码实现
首先，需要处理一些一定不是回文的情况：
- 1、开头带符号的一定不是回文，例如 -123 、-1221，这种情况直接返回false
- 2、数字大于0，并且末尾数为0的，例如 10、100，这种情况直接返回false
接下来反转数字的一半：
- 1、例如数字1221，执行1221 % 10取模运算，得到最后一位数字1。
- 2、将数字1221除以10将最后一位数字移除，1221 / 10 = 122。
- 3、重复上面的操作，直到原始数字小于或等于反转后的数字，就说明到达原始数字位数的一半了。
public class Solution { public bool IsPalindrome(int x) { // 当 x < 0 时，x 不是回文数。 // 当 x ！= 0，并且尾数等于0 ，x 不是回文数 if (x < 0 || (x % 10 == 0 && x != 0)) { return false; } int revertedNumber = 0; while (x > revertedNumber) { revertedNumber = revertedNumber * 10 + x % 10; x /= 10; } // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。 // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123， // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。 return x == revertedNumber || x == revertedNumber / 10; } } 复制代码
执行结果：
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度： O(log n)
对于每次迭代，我们会将输入除以 1010，因此时间复杂度为 O(log n)。
空间复杂度： O(1)
有常数级个变量，所以空间复杂度为O(1)。
三、总结
需要注意的一个点就是由于回文数的位数可奇可偶，所以当它的长度是偶数时，它对折过来应该是相等的。
当它的长度是奇数时，那么它对折过来后，有一个的长度需要去掉一位数（除以 10 并取整）。
