每天一道算法：回文整数

10、回文整数

题目

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

示例1：

示例2：

示例3：

思路

1、递归法

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

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

2、对半法

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

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

代码

python实现