一些学算法-9. 回文数

一、题目

LeetCode-9. 回文数
链接：https://leetcode-cn.com/problems/palindrome-number/

难度：简单
给你一个整数x，如果x是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

示例 1：
输入：x = 121
输出：true

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

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

示例 4：
输入：x = -101
输出：false

提示：

• -2^31 <= x <= 2^31 - 1

二、解题思路

本题与一起学算法-7.整数反转其实是类似的，可以使用同样的思路求解。

回文数是对称的，根据这一特点我们可以把后半段取出来进行反转。

这里需要注意的一个问题是由于我们不知道回文数的位数个数，所以当位数是偶数的时候，对折是相等的；而位数是奇数的时候，对折后需要去掉一位才相等。

除此之外，我们可以根据回文数的特点先排除一些数，即负数和末尾为零的数。负数肯定不对称，末尾为零包括0也是不对称的，都不是回文数。

三、实现过程

c++

class Solution {
public:
    bool isPalindrome(int x) {
        //处理特殊情况
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber / 10;
    }
};

PHP

class Solution {

    /**
     * @param Integer $x
     * @return Boolean
     */
    function isPalindrome($x) {
        //处理特殊情况
        if ($x < 0 || ($x % 10 == 0 && $x != 0)) {
            return false;
        }
        $revertedNumber = 0;
        while ($x > $revertedNumber) {
            $revertedNumber = $revertedNumber * 10 + $x % 10;
            $x = intval($x/10);
        }
        return $x == $revertedNumber || $x == intval($revertedNumber / 10);
    }
}

JavaScript

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
        //处理特殊情况
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        let revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x = parseInt(x/10);
        }
        return x == revertedNumber || x == parseInt(revertedNumber / 10);
};

四、小结

1. 时间复杂度：O(logx)。
2. 空间复杂度：O(1)