【刷题记录】9. 回文数

一、题目描述

来源：力扣（LeetCode）

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

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121

输出：true

示例 2：

输入：x = -121

输出：false

解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

输入：x = 10

输出：false

解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：

-

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

二、思路分析

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;
    }
}

复杂度分析

时间复杂度：

空间复杂度：

运行结果

总结

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