回文数[简单]

回文数[简单]"/>

回文数[简单]

优质博文：IT-BLOG-CN

一、题目

给你一个整数x，如果x是一个回文整数，返回true；否则返回false。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121是回文，而123不是。

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

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

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

-2^31 <= x <= 2^31 - 1

进阶： 你能不将整数转为字符串来解决这个问题吗？

二、代码

思路： 第一个想法是将数字转换为字符串，并检查字符串是否为回文。但是，这需要额外的非常量空间来创建问题描述中所不允许的字符串。第二个想法是将数字本身反转，然后将反转后的数字与原始数字进行比较，如果它们是相同的，那么这个数字就是回文。 但是，如果反转后的数字大于int.MAX，我们将遇到整数溢出问题。

按照第二个想法，为了避免数字反转可能导致的溢出问题，为什么不考虑只反转int数字的一半？毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。例如，输入1221，我们可以将数字1221的后半部分从21反转为12，并将其与前半部分12进行比较，因为二者相同，我们得知数字1221是回文。

首先，我们应该处理一些临界情况。所有负数都不可能是回文，例如：-123不是回文，因为-不等于3。所以我们可以对所有负数返回false。除了0以外，所有个位是0的数字不可能是回文，因为最高位不等于0。所以我们可以对所有大于0且个位是0的数字返回false。

现在，让我们来考虑如何反转后半部分的数字。对于数字1221，如果执行1221 % 10，我们将得到最后一位数字1，要得到倒数第二位数字，我们可以先通过除以10把最后一位数字从1221中移除，1221 / 10 = 122，再求出上一步结果除以10的余数，122 % 10 = 2，就可以得到倒数第二位数字。如果我们把最后一位数字乘以10，再加上倒数第二位数字，1 * 10 + 2 = 12，就得到了我们想要的反转后的数字。如果继续这个过程，我们将得到更多位数的反转数字。

现在的问题是，我们如何知道反转数字的位数已经达到原始数字位数的一半？由于整个过程我们不断将原始数字除以10，然后给反转后的数字乘上10，所以，当原始数字小于或等于反转后的数字时，就意味着我们已经处理了

class Solution {public boolean isPalindrome(int x) {// 思路：因为不能使用字符串和反转整个整数，因为反转后数int溢出，所以只能创建一个变量保存一般的数据，利于/和%// 第一步：先排除特殊的场景，但是0是符合的if (x < 0 ||  (x > 0 && x % 10 == 0)) {return false;}// 第二步：创建一个变量保存 % 后的数据，并对当前x进行/操作int temp = 0;while (x > temp) {// 退出条件：x不断减小， temp不断变大，最终就会退出，先让原有的数进一为给尾数留个坑位temp = temp * 10 + x % 10;x = x / 10;}// 第三步，判断x与temp是否相同，特殊场景判断：当x为奇数时 temp 会比 x多以为，比如 12321 进行上面的拆分后 x = 12 temp = 123，所以需要对 temp进行 /return temp == x || temp /10  == x;}
}

时间复杂度： O(log⁡n)对于每次迭代，我们会将输入除以10，因此时间复杂度为O(log⁡n)。
空间复杂度： O(1)我们只需要常数空间存放若干变量。