9. 回文数
题目描述
输入一个整数 x。如果把它的十进制写法从左往右读和从右往左读完全相同，它就是回文数。
x 是回文数时返回 true，否则返回 false。比如 121 是回文数，123 不是。负数带有负号，反过来读时负号在末尾，所以负数都不是回文数。
示例 1
输入：x = 121 输出：true
示例 2
输入：x = -121 输出：false
解释：反过来读是 121-，与原数不同。
示例 3
输入：x = 10 输出：false
解释：反过来读是 01，与 10 不同。
数据范围
-2^31 <= x <= 2^31 - 1
进阶：能否不把整数转成字符串就完成判断？
解题思路：反转一半数字
只反转后一半数字：每次把 x 的最低位搬到 rev 末尾，直到 rev >= x，此时恰好搬走了一半（奇数位时 rev 多一位中间数字）。然后比较 x == rev（偶数位）或 x == rev // 10（奇数位，去掉中间位）。末尾是 0 的正数不可能是回文，要提前排除，否则 10 会被误判。
为什么正确
循环中，x 的数字 + 反序的 rev 数字正好拼回原数；rev 是原数后半段的反转。
复杂度分析
时间 O(log x)，只处理一半位数；空间 O(1)。
易错点
忘记排除末尾为 0 的数：x = 10 时 rev 变成 0 后 x = 1，会因 x == rev // 10 被误判为回文。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0 or (x % 10 == 0 and x != 0):
return False
rev = 0
while x > rev:
rev = rev * 10 + x % 10
x //= 10
return x == rev or x == rev // 10class Solution {
public boolean isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int rev = 0;
while (x > rev) {
rev = rev * 10 + x % 10;
x /= 10;
}
return x == rev || x == rev / 10;
}
}class Solution {
public:
bool isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int rev = 0;
while (x > rev) {
rev = rev * 10 + x % 10;
x /= 10;
}
return x == rev || x == rev / 10;
}
};func isPalindrome(x int) bool {
if x < 0 || (x%10 == 0 && x != 0) {
return false
}
rev := 0
for x > rev {
rev = rev*10 + x%10
x /= 10
}
return x == rev || x == rev/10
}var isPalindrome = function(x) {
if (x < 0 || (x % 10 === 0 && x !== 0)) {
return false;
}
let rev = 0;
while (x > rev) {
rev = rev * 10 + x % 10;
x = Math.floor(x / 10);
}
return x === rev || x === Math.floor(rev / 10);
};function isPalindrome(x: number): boolean {
if (x < 0 || (x % 10 === 0 && x !== 0)) {
return false;
}
let rev = 0;
while (x > rev) {
rev = rev * 10 + x % 10;
x = Math.floor(x / 10);
}
return x === rev || x === Math.floor(rev / 10);
}其他解法
主解法把后半段反转后与前半段比较；备选解法用除数从两端向中间双指针式比较。两者复杂度相同。
解法 2：首尾数位对比 时间 O(log x)，空间 O(1)
先求出与 x 位数相同的 div=10^(位数-1)，则 x/div 是最高位，x%10 是最低位。两者不等就不是回文；相等则用 (x%div)/10 同时去掉首尾两位，div 除以 100，继续比较。
直接对应「对称位置相等」的回文定义，完全不生成新数，因此不存在溢出问题。内部带 0 的情况（如 1001）依靠 div 每次除以 100 自然处理，需要想清楚才不易写错。
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
div = 1
while x // div >= 10:
div *= 10
while x > 0:
if x // div != x % 10:
return False
x = (x % div) // 10
div //= 100
return Trueclass Solution {
public boolean isPalindrome(int x) {
if (x < 0) return false;
int div = 1;
while (x / div >= 10) div *= 10;
while (x > 0) {
if (x / div != x % 10) return false;
x = (x % div) / 10;
div /= 100;
}
return true;
}
}class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) return false;
int div = 1;
while (x / div >= 10) div *= 10;
while (x > 0) {
if (x / div != x % 10) return false;
x = (x % div) / 10;
div /= 100;
}
return true;
}
};func isPalindrome(x int) bool {
if x < 0 {
return false
}
div := 1
for x/div >= 10 {
div *= 10
}
for x > 0 {
if x/div != x%10 {
return false
}
x = (x % div) / 10
div /= 100
}
return true
}var isPalindrome = function(x) {
if (x < 0) return false;
let div = 1;
while (Math.floor(x / div) >= 10) div *= 10;
while (x > 0) {
if (Math.floor(x / div) !== x % 10) return false;
x = Math.floor((x % div) / 10);
div = Math.floor(div / 100);
}
return true;
};function isPalindrome(x: number): boolean {
if (x < 0) return false;
let div = 1;
while (Math.floor(x / div) >= 10) div *= 10;
while (x > 0) {
if (Math.floor(x / div) !== x % 10) return false;
x = Math.floor((x % div) / 10);
div = Math.floor(div / 100);
}
return true;
};