【刷题记录】9. 回文数

一、题目描述

来源：力扣（LeetCode）

给你一个整数 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$

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

二、思路分析

1. 转字符串

不考虑进阶的话，最直接的就是将整数 x 转化为字符串 s1，然后直接利用函数将字符串反转为 s2，与原字符串 s1 比较是否相等，即可得到结果。

2.反转数字

2.1 反转整个数字

与之前题目 【刷题记录】7. 整数反转 中的思路类似。将整数反转之后再与原数字相比较。多个判断就是 负数和 x%10 == 0 的数组不可能是回文数

2.2 反转一半的数组

上面方法处理的时候还需要处理反转后数组溢出等情况，我们可以再优化一下。

因为如果数字是回文数，其后半部分反转后应该与原始数字的前半部分相同。

例如，输入 1221，我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”， 并将其与前半部分 “12” 进行比较，因为二者相同，我们得知数字 1221 是回文。

所以我们只需要得到回文的后半部分数，与前面比较即可，取数的方法跟反转整数类似。

三、代码实现

class Solution {    public boolean isPalindrome(int x) {        // 负数和 10的倍数的 直接返回        if (x < 0 || (x % 10 == 0 && x != 0)) {            return false;        }
        int revertedNum = 0;        while (x > revertedNum) {            revertedNum = revertedNum * 10 + x % 10;            x /= 10;        }
        // 回文数 长度奇偶两种情况        return x == revertedNum || x == revertedNum / 10;    }}

复杂度分析

时间复杂度：$O(logn)$

空间复杂度：$O(1)$

运行结果

总结

这个题目其实可以算是反转类型的一种，我们只要掌握了一种，形式上再变，其实都是大差不差的。