Leetcode 每日一题9.回文数

🌈🌈🌈今天给大家分享的是:回文数的解法

编辑

问题描述

输入输出格式

示例

约束条件

进阶挑战

解决方案

问题分析

过题图片

字符串转换法

数学方法

算法解释

题目链接

结论

问题描述

给定一个整数 x，我们需要判断它是否是一个回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文数，而 123 不是。

输入输出格式

输入：一个整数 x。
输出：如果 x 是回文数，返回 true；否则，返回 false。

示例

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

约束条件

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

进阶挑战

不将整数转为字符串，解决这个问题。

解决方案

问题分析

要判断一个整数是否为回文数，我们可以采用两种方法：

字符串转换法：将整数转换为字符串，然后使用双指针从两端向中间遍历，比较字符是否相等。
数学方法：通过数学运算，反转整数的一半数字，然后比较反转后的数字与原始数字的前半部分是否相等。

过题图片

字符串转换法

这种方法简单直观，但不符合进阶挑战的要求。以下是使用字符串转换法的代码实现：

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        String num = Integer.toString(x);
        int l = 0, r = num.length() - 1;
        while (l < r) {
            if (num.charAt(l) != num.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}

数学方法

这种方法不需要将整数转换为字符串，而是通过数学运算来实现。以下是使用数学方法的代码实现：

class Solution {
    public boolean isPalindrome(int x) {
        // 负数和以0结尾的非0数不是回文数
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        
        int reversedHalf = 0, original = x;
        while (x > 0) {
            int pop = x % 10;
            x = x / 10;
            reversedHalf = reversedHalf * 10 + pop;
        }
        
        // 对于奇数长度的回文数，我们只需要判断前半部分
        return original == reversedHalf || original == reversedHalf / 10;
    }
}

算法解释

负数和以0结尾的非0数不是回文数：首先，我们排除负数和以0结尾的非0数，因为它们不可能是回文数。
反转整数的一半数字：通过 while 循环，我们不断地取出 x 的最低位数字，并将其加到 reversedHalf 的末尾。同时，我们将 x 除以10，去掉最低位数字。
比较反转后的数字与原始数字的前半部分：最后，我们比较原始数字 original 与反转后的数字 reversedHalf 是否相等。对于奇数长度的回文数，我们只需要比较 original 与 reversedHalf 除以10的结果是否相等。