每日一道算法：回文数

题目：判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例1：
输入: 121
输出: true

示例2：
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数

示例3：
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数

解法：反转一半数字

思路分析：

第一想到的两种办法是：
1、通过整数转换字符串反转后判断两数是否相等（时间复杂度O(n)） 
2、数学方法全反转(时间复杂度O(logn))
以上两种方法可以解决，但不是最优的，因为还需要判断是否益处
最佳的方法：还是使用数学方法进行反转，但是只需反转一半即可

PHP代码实现：

/**
 * @param Integer $x
 * @return Boolean
 */
function isPalindrome($x){
    //特殊情况
    //1、小于0的负数肯定不是回文数
    //2、最后一位是0，且第一位也不是0，肯定不是回文数
    if($x < 0 || ($x%10 == 0 && $x != 0)){
        return false;
    }
    $res = 0;//反转后的数
    while($x > $res){//当x小于等于res时，即已经反转一半了
        $res = $res*10 + $x%10;
        $x = intval($x/10);//需要使用intval强制把浮点转整型
    }
    //当x的位数为偶数时，比如1221，循环的最后，x=12，res=12
    //当x的位数为奇数时，比如12321，循环的最后，x=12，res=123，但中间的位数对于回文数没有影响，所以res除以10可以剔除掉
    return $x == $res || $x == intval($res/10);
}

使用：
var_dump(isPalindrome(121));

复杂度分析：

时间复杂度：O(log10(n))
对于每次迭代，我们会将输入除以10
时间复杂度：O(1)

github

以后每次题解都会上传到这个项目

LeetCode_PHP：https://github.com/zhangdejian/LeetCode_PHP

题目来源

力扣（LeetCode）：https://leetcode-cn.com/problems/palindrom...

本作品采用《CC 协议》，转载必须注明作者和本文链接