🚩传送门：牛客题目

题目

在不使用额外的内存空间的条件下判断一个整数是否是回文。

示例 1：

输入：x = 121 输出：true

示例 2

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

示例 3：

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

示例 4：

输入：x = -101 输出：false

解题思路1：字符串

最简单的解法就是先将 整数转为字符串 ，然后将字符反转进行判断对应元素是否相等即可。

复杂度分析

时间复杂度：[NC]56. 回文数字 - 图1，其中 [NC]56. 回文数字 - 图2 为字符串的长度。

  1.   - 我们需要一次拷贝字符串然后依次比较是否相等。

空间复杂度：[NC]56. 回文数字 - 图3

  1.   - 我们需要一个长度为   ![](https://cdn.nlark.com/yuque/__latex/7b8b965ad4bca0e41ab51de7b31363a1.svg#card=math&code=n%0A&id=e08X2)  的字符数组数组存放字符串。

官方代码

  1. ///简单粗暴，看看就行
  2. class Solution {
  3.     public boolean isPalindrome(int x) {
  4.         String reversedStr = (new StringBuilder(x + "")).reverse().toString();
  5.         return (String.valueOf(x)).equals(reversedStr);
  6.     }
  7. }

解题思路2：取整取余逐位比较

通过取整和取余操作获取整数中对应的数字进行比较。

举个例子：1221 这个数字。

  • 通过计算 1221 / 1000， 得首位 _1_
  • 通过计算 1221 % 10， 得末位 _1_
  • 进行比较
  • 再将 22 取出来继续比较

[NC]56. 回文数字 - 图4

复杂度分析

时间复杂度：[NC]56. 回文数字 - 图5，其中 [NC]56. 回文数字 - 图6 为数字位数。

  1.   - 我们需要遍历每一位获取位数

空间复杂度：[NC]56. 回文数字 - 图7

  1.   - 我们需要常量空间。

官方代码

  1. class Solution {
  2.     public boolean isPalindrome(int x) {
  3.         //边界判断
  4.         if (x < 0) return false;
  5.         int div = 1;
  6.         //
  7.         while (x / div >= 10) div *= 10;    // 获取新数字的位数
  8.         while (x > 0) {
  9.             int left = x / div;
  10.             int right = x % 10;
  11.             if (left != right) return false;
  12.             x = (x % div) / 10;              // 获取 22 
  13.             div /= 100;                        // 获取新数字的位数
  14.         }
  15.         return true;
  16.     }
  17. }

解题思路2：反转一半数字

映入脑海的第一个想法是将数字转换为字符串，并检查字符串是否为回文。但是，这需要额外的非常量空间 。

第二个想法是将数字本身反转，然后将反转后的数字与原始数字进行比较，如果相同，那么这个数字就是回文。
但是，如果反转后的数字大于 int.MAX，我们将遇到整数溢出问题。

按照第二个想法，为了避免数字反转可能导致的溢出问题，为什么不考虑只反转 int 数字的一半？毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。

例如：输入 1221，我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”，并将其与前半部分 “12” 进行比较，因为二者相同，我们得知数字 1221 是回文。

首先，我们应该处理一些临界情况。

  1. 所有负数都不可能是回文，因为负号和个位不相等。
  2. 除了 0 以外，所有个位是 0 的数字不可能是回文，因为最高位不等于 0。

现在，让我们来考虑如何反转后半部分的数字。

对于 1221

  1. 执行 1221 % 10，我们将得到最后一位数字 1
  2. 要得到倒数第二位数字，我们可以先通过除以 10 把最后一位数字从 1221 中移除，1221 / 10 = 122，再求出上一步结果除以 10 的余数，122 % 10 = 2，就可以得到倒数第二位数字。
  3. 我们把最后一位数字乘以 10，加上倒数第二位数字，1 * 10 + 2 = 12，就得到了我们想要的反转后的数字。
  4. 如果继续这个过程，我们将得到更多位数的反转数字。

现在的问题是，我们如何知道反转数字的位数已经达到原始数字位数的一半？

由于整个过程我们不断将原始数字除以 10，然后给反转后的数字乘上 10，所以，当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了。
[NC]56. 回文数字 - 图8

复杂度分析

时间复杂度：[NC]56. 回文数字 - 图9，对于每次迭代，我们会将输入除以 10，因此时间复杂度为[NC]56. 回文数字 - 图10。

空间复杂度：[NC]56. 回文数字 - 图11，我们只需要常数空间存放若干变量 。

官方代码

  1. class Solution {
  2.     public boolean isPalindrome(int x) {
  3.         // 当 x < 0 时,x 不是回文数。
  4.         // 数字的最后一位是 0,且第一位数字不是 0
  5.         if (x < 0 || (x % 10 == 0 && x != 0)) {
  6.             return false;
  7.         }
  8.         int revertedNumber = 0;
  9.         while (x > revertedNumber) {
  10.             revertedNumber = revertedNumber * 10 + x % 10;
  11.             x /= 10;
  12.         }
  13.         // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
  14.         return x == revertedNumber || x == revertedNumber / 10;
  15.     }
  16. }