LeetCode9：回文数

原题地址：. - 力扣（LeetCode）

题目描述：

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数

是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

• 例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

示例 2：

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

示例 3：

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

提示：

• -231 <= x <= 231 - 1

解题思路：

解题思路

1. 首先，我们检查整数是否为负数。如果是负数，直接返回false，因为负数不可能是回文数。
2. 接着，我们检查整数是否为一位数。如果是一位数，它自然是回文数，直接返回true。
3. 然后，我们将整数转换为字符串，再将字符串转换为字符数组。这样做是为了方便比较每一位数字。
4. 我们计算字符数组的中间位置，只需要遍历数组的一半进行比较。
5. 使用一个循环，我们比较字符数组中对称位置上的数字。如果任何一对对称位置上的数字不相等，我们立即返回false。
6. 如果循环结束后没有找到不相等的数字对，说明整数是回文数，返回true。

时间复杂度

时间复杂度是 O(n/2)，其中 n 是整数的位数。由于我们只需要遍历整数的一半位数来比较数字，所以时间复杂度是整数位数的一半。在大 O 记号中，常数因子会被忽略，因此时间复杂度简化为 O(n)。

空间复杂度

空间复杂度是 O(n)，因为我们需要将整数转换为一个字符数组来存储每一位数字，这个数组的长度与整数的位数成正比。此外，我们没有使用其他与输入大小成比例的额外空间

代码实现：

class Solution {
    /**
     * 判断一个整数是否是回文数。
     * 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
     * @param x 需要判断的整数
     * @return 如果是回文数返回true，否则返回false
     */
    public boolean isPalindrome(int x) {
        // 如果整数是负数，它不可能是回文数，因为负号在反转后不会出现
        if(x < 0) {
            return false;
        }
        // 一位数的整数总是回文数
        if(x >= 0 && x < 10) {
            return true;
        }
        // 将整数转换为字符数组，以便比较每一位数字
        char[] c = String.valueOf(x).toCharArray();
        // 计算数组的中间位置
        int midden = c.length / 2;
        // 遍历数组的一半，比较对称位置上的数字是否相等
        for(int i = 0; i < midden; i++) {
            // 如果对称位置上的数字不相等，则不是回文数
            if(c[i] != c[c.length - i - 1]) {
                return false;
            }
        }
        // 如果所有对称位置上的数字都相等，则是回文数
        return true;
    }
}