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

> 推荐阅读

>

> - CSDN主页

> - GitHub开源地址

>- Unity3D插件分享

> - 简书地址

> - 我的个人博客

> - QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

## 一、题目

### 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、重复上面的操作，直到原始数字小于或等于反转后的数字，就说明到达原始数字位数的一半了。

```csharp

public class Solution

{

​ public bool IsPalindrome(int x)

​ {

​ // 当 x < 0 时，x 不是回文数。

​ // 当 x ！= 0，并且尾数等于0 ，x 不是回文数

​ if (x < 0 || (x % 10 == 0 && 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;

​ }

}

```

执行结果：

### 3、时间复杂度

时间复杂度： O(log n)

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

空间复杂度： O(1)

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

## 三、总结

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

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