[力扣_9] 回文数
题目入口:点击进入
相关算法:
- 整数的基本运算——时间复杂度:O(logn),对于每次迭代,我们会将输入除以 1010,空间复杂度:O(1)
思路和算法:
首先通过题目给出的样例我们可以知道以下几种情况:
- 当给定的x为负数的时候,不可能为回文,直接返回false
- 当给定的x小于10(为一位数)的情况,肯定是回文,直接返回true
以及一些边界条件,因为我们已经不考虑将其转化成字符串了,所以我们会面临整数越界的情况:反转后大于:INT_MAX或小于INT_MIN
这题与我们之前的第7题类同,我们从第7题可以得出思路,用一个高精度的longlong类型来存储反转后的字符串,再将其转化成int类型,看与之想不想等
若相等,则该字符串是回文,返回true,若不想等,则该字符串不是回文,返回false
因为是一道简单题,且上述思路时间复杂度也与官方题解相差无几,所以这儿只记录自己的思路
如何反转给定的整数,这个和整数转化为字符串类同,我们可以将新的数:num
- num=num*10+(x%10)
- x=x/10
答题代码如下:
bool isPalindrome(int x){
if(x>=0&&x<10)//极端情况
{
return true;
}
if(x<0)
{
return false;
}
long long nums=0;//高精度存储,给定的是整数类型,反转后必定不会超过longlong的范围
int y=x;
while(y>0)
{
nums=nums*10+(y%10);
y=y/10;
}
if((int)nums==x)
{
return true;
}
return false;
}
若有兴趣可参考评论区的各路大神扩展自己的思路。