欢迎光临散文网 会员登陆 & 注册

回文数

2023-07-12 11:14 作者:MicroShuai  | 我要投稿


第一次(自己)解法思路 :

把数字转化为字符串,在转化为char类型的数组,然后用两个指针前后比较


时间复杂度 和 空间复杂度 都为 O(n) 

  • 时间复杂度分析 : O(log n + n)  ≈ O(n)。

    • 符串转换:将整数转换为字符串需要花费 O(log n) 的时间,其中 n 是输入整数的位数。

    • 对称比较:在对称比较过程中, O(n/2)  O(n) 的时间,其中 n 是字符串的长度。

  • 空间复杂度分析:O(log n + n)  ≈ O(n)

    • 字符串转换:将整数转换为字符串需要使用额外的存储空间,其空间复杂度为 O(log n)

    • 字符数组:将字符串转换为字符数组需要额外的存储空间,其空间复杂度为 O(n)

第二次解法(数学法):

把后面一半的数字反转之后与截取之后的数字进行比较

时间复杂度 :O(lngN) 截取一半  

空间复杂度 :  O(1) 没有开辟新的空间  

代码分析:(优秀的代码需要严谨)

            首先排除 小于0的数 和 二位整数(让0通过)

            然后定义一个变量 reversedNumber 去 保存每次截取反转 后 的 数字

            这里是< 而不是<=  如果 为<= ,那么当输入0 的时候会导致死循环

            最后写出 奇数 偶数 两种情况的判断 

            为什么奇数需要/10? 因为截取之后 奇数比截取之后的数多一位,使用需要/10



有关上一章节中的“异或”运算符 的“额外” 小运用:

         交换两个变量的值

 但是不推荐这样去使用,虽然性能比创建临时变量的性能高,但是可读性差,并且不符合代码规范

         判断奇偶

如果一个数为偶数 那么二进制最后一位肯定为 0 ,反之为1;

那么就可以用 & 或者 | 去判断 奇偶

回文数的评论 (共 条)

分享到微博请遵守国家法律