10、回文整数
题目
判断一个整数是否是一个回文数(后往前读与从前往后读一样)。
示例1:
示例2:
示例3:
思路
1、递归法
实现一个递归函数,每次比较一个数的最高位和最低位是否相等,然后去掉最高位和最低位,继续判断。
设整数位数为 n,则计算位数需要循环次数为 n,递归的循环次数为 n/2,因此整体循环次数为 1.5n。
2、对半法
提取整数的一半进行反转,然后与另一半对比是否相等。循环次数为 n/2。
虽然严格来说两个方法的时间复杂度都为 O(n),但是循环次数相差了3倍。对半法充分利用了整数可以直接判断大小的性质,减少了循环次数。
代码
python实现
领取专属 10元无门槛券
私享最新 技术干货