回文数[简单]

刺骨的言语ヽ痛彻心扉 2024-02-19 07:51 10阅读 0赞

优质博文：[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)`我们只需要常数空间存放若干变量。

[IT-BLOG-CN]: https://it-blog-cn.com/blogs/algorithm/topic/easy/palindrome_num