☆打卡算法☆LeetCode 9、判断回文数 算法解析

一、题目

1、算法题目

“判断给定的整数是否是一个回文数。”

题目链接： 来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/palindrome-number/

2、题目描述

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

回文数是指正序（从左到右）和倒序（从右到左）读都是一个整数。例如，121 是回文，而 123 不是。

比如：

输入：x = 121 输出：true

输入：s = "-121" 输出：false 解析：从左向右读-121,从右向左读123-，并不是一个回文数。

二、解题

1、思路分析

这道题第一个想法是将数字转换成字符串，然后检查字符串是否为回文，但是这个需要额外的空间来创建字符串。

第二个想法是直接将数字本身反转，然后将反转后的数字与原始数字进行比较，如果相同，那么这个整数就是回文。

但是，可能会出现反转后的数字大于INT.MAX的情况，也就是整数溢出。

那么按照第二个想法，为了避免整数溢出问题，可以考虑只反转数字的一半，例如，1221，将数字12反转为21，与后半部分21比较，因为二者相同，所以数字1221是回文。

2、代码实现

首先，需要处理一些一定不是回文的情况：

• 1、开头带符号的一定不是回文，例如 -123 、**-1221**，这种情况直接返回false
• 2、数字大于0，并且末尾数为0的，例如 10、100，这种情况直接返回false

接下来反转数字的一半：

• 1、例如数字1221，执行1221 % 10取模运算，得到最后一位数字1。
• 2、将数字1221除以10将最后一位数字移除，1221 / 10 = 122。
• 3、重复上面的操作，直到原始数字小于或等于反转后的数字，就说明到达原始数字位数的一半了。

public class Solution 
{
    public bool IsPalindrome(int x) 
    {
        // 当 x < 0 时，x 不是回文数。
        // 当 x ！= 0，并且尾数等于0 ，x 不是回文数
        if (x < 0 || (x % 10 == 0 &amp;&amp; x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

执行结果：

image.png

3、时间复杂度

时间复杂度： O(log n)

对于每次迭代，我们会将输入除以 1010，因此时间复杂度为 O(log n)。

空间复杂度： O(1)

有常数级个变量，所以空间复杂度为O(1)。

三、总结

需要注意的一个点就是由于回文数的位数可奇可偶，所以当它的长度是偶数时，它对折过来应该是相等的。

当它的长度是奇数时，那么它对折过来后，有一个的长度需要去掉一位数（除以 10 并取整）。