【刷题记录】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;
 }
}


复杂度分析

时间复杂度：

空间复杂度：

运行结果

总结

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