LeetCode 9. 回文数
题目描述
✅ 9. 回文数
题意分析
判断整数的十进制表示从左到右和从右到左是否相同。负号也是表示的一部分，因此负数不是回文数；
0和所有非负的一位数都是回文数。非零整数不保留前导零，所以末位是零的正数不可能是回文。题目进阶要求不转成字符串，可以直接操作数字位；只需返回是否回文，不必得到整个数字的反转结果。
解法：反转后一半数字
核心思路
[!blue]
回文只要求前半段与反转后的后半段一致，中间一位可以不参与比较。因此保留
x作为尚未处理的高位，用reverted从零开始保存已经取走的低位的逆序。每轮通过x % 10取出末位，用reverted * 10 + x % 10将它接到反转部分，再通过x /= 10删除原末位。先排除负数和非零尾零数后，原末位不是零，反转部分不会因前导零丢失位数。在取走不足一半数位时，剩余
x的位数更多，必有x > reverted，应继续处理。反转部分追上或超过剩余部分后，才达到需要比较中间位置的阶段，循环条件因而使用x > reverted。若原数有偶数位且是回文，两半相等时恰好停止，检查
x == reverted即可。若有奇数位，反转部分会多包含一个中间数字，它处在reverted的个位；去掉这一位后，用x == reverted / 10比较两侧。中间数字本来就与自身对称，不影响回文性。非回文的偶数位数在两半位数相同时可能仍有
x > reverted，这时会多取一位，但最后两个相等条件都不会通过：反转部分的位数已经超过能够配对的范围。算法不需要预先知道位数或奇偶，只需同时检查这两个结束条件。只反转约一半数位，避免构造可能超出整数范围的完整反转值。
0不进入循环，两部分仍为零，最终自然返回true。
解题步骤
- 若
x < 0，或x非零且末位为零，返回false。- 初始化
reverted = 0，当x > reverted时，取出x末位追加到reverted，再删除x末位。- 循环结束后，若
x == reverted或x == reverted / 10，返回true；否则返回false。
代码实现
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(1)$，只保存剩余高位和已经反转的低位。
关键点总结
[!green]
- 排除非零尾零数，保证逆序部分不会因为前导零而丢失位数。
- 将末位逐个搬到反转部分，用两侧大小关系决定何时停止。
- 偶数位直接比较两半，奇数位先丢掉反转部分末尾的中间位。
- 完整反转不是判定所必需的信息，保留一半即可避免其溢出问题。
易错点总结
[!yellow]
- 将所有末位为零的数都判为失败，会错误排除
0，尾零特判必须同时要求非零。- 不排除非零尾零数，反转部分会丢掉前导零，可能使奇数位的比较条件错误成立。
- 使用
x >= reverted作为循环条件，会在偶数位两半已经相等时继续拆位；输入零还会一直停在零而无法结束。- 只保留一种结束比较，无法同时覆盖奇数位和偶数位的回文数。
- 为负数取绝对值再判断，忽略了负号导致其本身不是回文的题意。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 7. 整数反转 | 中等 | 反转数字的取余与除法可复用，本题反转一半即可，避免完整反转的溢出风险。 |
| 125. 验证回文串 | 简单 | 同样比较正反两端，本题直接操作数字位，原题还需过滤字符并忽略大小写。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！