每天一道算法:回文整数

10、回文整数

题目

判断一个整数是否是一个回文数(后往前读与从前往后读一样)。

示例1:

示例2:

示例3:

思路

1、递归法

实现一个递归函数,每次比较一个数的最高位和最低位是否相等,然后去掉最高位和最低位,继续判断。

设整数位数为 n,则计算位数需要循环次数为 n,递归的循环次数为 n/2,因此整体循环次数为 1.5n。

2、对半法

提取整数的一半进行反转,然后与另一半对比是否相等。循环次数为 n/2。

虽然严格来说两个方法的时间复杂度都为 O(n),但是循环次数相差了3倍。对半法充分利用了整数可以直接判断大小的性质,减少了循环次数。

代码

python实现

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180918G09MSY00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券