LeetCode 9. 回文数
目录
题目描述
✅ 9. 回文数
题意分析
给一个 32 位有符号整数
x，判断它的十进制表示正着读和倒着读是否完全一样。注意判断对象是「十进制表示」本身，包括符号在内的书写形式，而不是数值的某种抽象性质。约束里
x的范围是-2^31到2^31 - 1，也就是紧贴int边界。这个信号很重要：任何试图先算出「把x整个倒过来写」对应的那个数的做法，都可能造出一个超过int上限的中间量，例如1999999999倒过来是9999999991，已经放不进int。进阶部分还明确要求不把整数转成字符串，这等于封掉了最省事的那条路，逼着解法在数值层面操作。边界集中在四处。负数一律不是回文，因为负号只写在最左边，倒过来读会跑到最右边；末尾是
0的正数也一律不是回文，因为倒过来最高位就成了0，而正数的十进制表示不允许前导零；唯一的例外是0本身，它只有一位，正反都是0，必须判为回文；所有一位数同理都是回文。
解法：反转后一半数字
核心思路
问题关键：完整反转整数可能溢出，而判断回文只需要比较前后两半，没有必要反转全部数位。
为什么选反转后一半：每轮把
x的末位移到reverted，当x <= reverted时已经处理到中点。反转值最多只有原数一半左右的位数，避开完整反转的溢出问题，也不需要转成字符串。循环不变量：
x保存尚未处理的高位前缀，reverted保存已处理低位的逆序；每轮恰好从前者末尾搬一位到后者末尾。正确性：偶数位回文在中点处满足
x == reverted；奇数位时reverted多包含中间位，去掉它后满足x == reverted / 10。非回文数的镜像两半不满足任一条件。负数有负号，非零且末位为 0 的数倒序后会产生前导 0，因此先排除；0单独保留为回文。
解题步骤
x < 0，或x != 0 && x % 10 == 0时返回false。- 初始化
reverted = 0；当x > reverted时，取出x的末位拼到reverted，再删除x的末位。- 循环结束后，判断
x == reverted || x == reverted / 10。口述样例：
1221依次变为(x,reverted) = (122,1) → (12,12)，偶数位两半相等；12321最终为(12,123)，丢掉中位3后两半相等。
代码实现
class Solution {
public boolean isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int reverted = 0;
while (x > reverted) {
reverted = reverted * 10 + x % 10;
x /= 10;
}
return x == reverted || x == reverted / 10;
}
}
func isPalindrome(x int) bool {
if x < 0 || (x%10 == 0 && x != 0) {
return false
}
reverted := 0
for x > reverted {
reverted = reverted*10 + x%10
x /= 10
}
return x == reverted || x == reverted/10
}
复杂度分析
- 时间复杂度：$O(d)$，
d为十进制位数，即正数时为 $O(\log x)$；实际只处理约一半数位。- 空间复杂度：$O(1)$。
关键点总结
- 只构造判定所需的一半信息，既省操作又从结构上规避溢出。
x > reverted自然定位中点，不必预先统计位数。- 结尾的两个比较分别覆盖偶数位和奇数位，中间位不影响回文性。
- 面试时应主动指出完整反转的溢出风险；改用
long只是扩大边界，不如半反转稳健。
易错点总结
- 末位为 0 的特判必须排除
x = 0；否则唯一合法的零会被误判。- 不特判
10这类非零尾零数时，最终x == reverted / 10可能错误成立。- 循环条件应为
x > reverted；写成>=会让1221在两半相等后多处理一位。- 只判断
x == reverted会漏掉12321，只判断x == reverted / 10会漏掉1221，两种长度必须同时覆盖。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 7. 整数反转 | 中等 | 必须真正输出反转值，无法回避溢出，需要在拼接前预判越界并返回零 |
| 8. 字符串转换整数 (atoi) | 中等 | 逐位构造数值，重点在空白、正负号解析与越界截断到边界值 |
| 125. 验证回文串 | 简单 | 载体是字符串，难点在过滤非字母数字字符并忽略大小写 |
| 234. 回文链表 | 简单 | 载体是单链表无法随机访问，需快慢指针定位中点再反转后半段 |
| 5. 最长回文子串 | 中等 | 从判定升级为搜索，用中心扩展或区间动态规划求最长的那一段 |
| 564. 寻找最近的回文数 | 困难 | 反向构造离目标最近的回文，需要枚举镜像候选并处理进位与位数变化 |