[力扣_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;
    
}

若有兴趣可参考评论区的各路大神扩展自己的思路。

本文链接:

https://nullcode.fun/55.html
1 + 9 =
快来做第一个评论的人吧~