今天我们来看一道经典的回文数题目，给定一个整数 x ，判断它是否是回文整数。如果 x 是一个回文数，则返回 true，否则返回 false。
回文数 是指从左往右读和从右往左读都相同的整数。例如，121 是回文，而 123 不是。
示例
-
示例 1
输入：x = 121
输出：true
解释：121 从左往右和从右往左都相同，因此是回文数。 -
示例 2
输入：x = -121
输出：false
解释：从左向右读为-121，从右向左读为121-。负号出现在末尾，因此不是回文数。 -
示例 3
输入：x = 10
输出：false
解释：从右向左读为01，与原数不相同。
思路解析
本题的核心是判断一个数字在正序和倒序上是否一致。一般地，可以想到两种解决方案：
-
字符串法：将整数转为字符串，判断字符串是否为回文。虽然这种方法简单直观，但它占用额外空间，不是最优解。
-
数学反转法：直接在数字层面反转整数的一半，再与另一半比较。这个方法通过操作数字本身，不使用额外空间，效率较高且实现优雅。
接下来，我们基于数学反转法优化解答。
优化的数学反转解法
在反转整数时，不需要整个数字的倒序，只需反转其一半。在反转过程中，如果反转后的数字与剩余的部分一致，说明该数字是回文。
优化步骤
-
负数直接排除：负数不可能是回文，因为其倒序会使负号出现在末尾。
-
非零且尾数为零的数字也可排除：如
10或100。若一个数的末尾是0，且它不是0本身，它就不可能是回文。 -
反转数字的一半：
- 每次将
x的最后一位拼接到reversedHalf后面，同时将x缩短一位，直到x的长度小于或等于reversedHalf。 - 如果数字的长度是偶数，则反转后的
reversedHalf与x应相等。 - 如果数字的长度是奇数，则可以忽略
reversedHalf的中间位（即reversedHalf / 10），此时两者也应相等。
- 每次将
代码实现
class Solution {
public:
bool isPalindrome(int x) {
// 负数或非零尾数为0的数无法成为回文数
if (x < 0 || (x % 10 == 0 && x != 0)) return false;
int reversedHalf = 0;
while (x > reversedHalf) {
reversedHalf = reversedHalf * 10 + x % 10;
x /= 10;
}
// 判断两种情况：
// 1. x == reversedHalf 表示偶数长度，反转完全相同
// 2. x == reversedHalf / 10 表示奇数长度，忽略中间一位
return x == reversedHalf || x == reversedHalf / 10;
}
};
代码详解
-
x < 0 || (x % 10 == 0 && x != 0)：这是排除负数和非零尾数为零的情况，这些数不可能是回文。 -
while (x > reversedHalf)：每次将x的最后一位加到reversedHalf后面，缩短x。这个过程在x的长度超过reversedHalf的长度时停止。 -
return x == reversedHalf || x == reversedHalf / 10：在循环结束后，有两种可能：- 若数字长度为偶数，则
x == reversedHalf。 - 若数字长度为奇数，则
x == reversedHalf / 10（忽略中间一位，见下面的例子）。
- 若数字长度为偶数，则
举例分析
以 x = 12321 为例，展示代码的运行过程：
- 初始化：
x = 12321，reversedHalf = 0 - 第一轮循环：
reversedHalf = reversedHalf * 10 + x % 10 = 0 * 10 + 1 = 1x = x / 10 = 1232
- 第二轮循环：
reversedHalf = 1 * 10 + 2 = 12x = 123
- 第三轮循环：
reversedHalf = 12 * 10 + 3 = 123x = 12
循环结束后，reversedHalf 是 123，x 是 12，可以看到 reversedHalf / 10 = 12，即 x == reversedHalf / 10 成立，因此 12321 是回文数。
复杂度分析
- 时间复杂度：O(log₁₀(n))，因为我们只遍历数字的一半。
- 空间复杂度：O(1)，不需要额外空间。
总结
这个方法不仅优化了空间使用，还保证了执行效率，是一种优雅的实现方案。通过这种方式，我们可以轻松判断整数是否为回文。该解法具有优秀的时间和空间复杂度，是回文数问题的最佳解法之一。
