一、题目
1、算法题目
“判断给定的整数是否是一个回文数。”
题目链接: 来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/pa…
2、题目描述
给你一个整数 x ,如果 x 是一个会问整数,返回 true;否则,返回 false。
回文数是指正序(从左到右)和倒序(从右到左)读都是一个整数。例如,121 是回文,而 123 不是。
比如:
输入:x = 121
输出:true
输入:s = "-121"
输出:false
解析:从左向右读-121,从右向左读123-,并不是一个回文数。
二、解题
1、思路分析
这道题第一个想法是将数字转换成字符串,然后检查字符串是否为回文,但是这个需要额外的空间来创建字符串。
第二个想法是直接将数字本身反转,然后将反转后的数字与原始数字进行比较,如果相同,那么这个整数就是回文。
但是,可能会出现反转后的数字大于INT.MAX的情况,也就是整数溢出。
那么按照第二个想法,为了避免整数溢出问题,可以考虑只反转数字的一半,例如,1221,将数字12反转为21,与后半部分21比较,因为二者相同,所以数字1221是回文。
2、代码实现
首先,需要处理一些一定不是回文的情况:
- 1、开头带符号的一定不是回文,例如 -123 、-1221,这种情况直接返回false
- 2、数字大于0,并且末尾数为0的,例如 10、100,这种情况直接返回false
接下来反转数字的一半:
- 1、例如数字1221,执行1221 % 10取模运算,得到最后一位数字1。
- 2、将数字1221除以10将最后一位数字移除,1221 / 10 = 122。
- 3、重复上面的操作,直到原始数字小于或等于反转后的数字,就说明到达原始数字位数的一半了。
public class Solution { public bool IsPalindrome(int x) { // 当 x < 0 时,x 不是回文数。 // 当 x != 0,并且尾数等于0 ,x 不是回文数 if (x < 0 || (x % 10 == 0 && x != 0)) { return false; } int revertedNumber = 0; while (x > revertedNumber) { revertedNumber = revertedNumber * 10 + x % 10; x /= 10; } // 当数字长度为奇数时,我们可以通过 revertedNumber/10 去除处于中位的数字。 // 例如,当输入为 12321 时,在 while 循环的末尾我们可以得到 x = 12,revertedNumber = 123, // 由于处于中位的数字不影响回文(它总是与自己相等),所以我们可以简单地将其去除。 return x == revertedNumber || x == revertedNumber / 10; } } 复制代码
执行结果:
网络异常,图片无法展示
|
3、时间复杂度
时间复杂度: O(log n)
对于每次迭代,我们会将输入除以 1010,因此时间复杂度为 O(log n)。
空间复杂度: O(1)
有常数级个变量,所以空间复杂度为O(1)。
三、总结
需要注意的一个点就是由于回文数的位数可奇可偶,所以当它的长度是偶数时,它对折过来应该是相等的。
当它的长度是奇数时,那么它对折过来后,有一个的长度需要去掉一位数(除以 10 并取整)。