0009. Palindrome Number¶
题目信息¶
- 题号:
回文数
- 难度:
Easy
- 主题:
数学、整数、回文
- 原题:
- 重点:
从字符串镜像比较,推导到直接处理十进制首尾数字,再用半反转删除位数统计与完整反转
题目重述¶
给定一个 32 位有符号整数 x,判断它的十进制表示从左向右和从右向左读取是否完全相同。
负数的十进制表示包含开头的负号,因此负数都不是回文数。数字 0 是回文数;非零且末位为
0 的整数不是回文数,因为正常十进制表示不会包含前导零。
x 的取值范围为 [-2^31, 2^31 - 1]。
自建示例¶
偶数位回文:
x = 4554,左右数字依次为4 == 4、5 == 5,返回true;奇数位回文:
x = 12321,中间数字3不需要配对,返回true;普通非回文:
x = 12341,首尾相同但内层2 != 4,返回false;非零末位零:
x = 120,反向表示需要不存在的前导零,返回false;负数:
x = -121,负号没有末尾镜像字符,返回false;零值:
x = 0,单个数字正反读取相同,返回true;单个正数位:
x = 7,返回true。
C++ 实现¶
#include <string>
class Solution {
private:
bool compareAsString(int x) {
if (x < 0) {
return false;
}
const std::string text = std::to_string(x);
int left = 0;
int right = static_cast<int>(text.size()) - 1;
while (left < right) {
if (text[left] != text[right]) {
return false;
}
++left;
--right;
}
return true;
}
bool compareOuterDigits(int x) {
if (x < 0) {
return false;
}
int divisor = 1;
while (x / divisor >= 10) {
divisor *= 10;
}
while (x != 0) {
const int first = x / divisor;
const int last = x % 10;
if (first != last) {
return false;
}
x = x % divisor / 10;
divisor /= 100;
}
return true;
}
bool reverseSecondHalf(int x) {
if (x < 0 || (x != 0 && x % 10 == 0)) {
return false;
}
int reversedHalf = 0;
while (x > reversedHalf) {
reversedHalf = reversedHalf * 10 + x % 10;
x /= 10;
}
return x == reversedHalf || x == reversedHalf / 10;
}
public:
bool isPalindrome(int x) {
return reverseSecondHalf(x);
}
};
题解¶
字符串镜像¶
回文定义最直接地表现为首尾字符逐对相等。把整数转换为字符串后,可以让 left 从左向右移动,
right 从右向左移动;任意一对字符不同就返回 false,所有镜像对都相同则返回 true。
compareAsString 完整对应这一判断过程,时间复杂度为 O(d),其中 d 是十进制位数。
它额外保存了 d 个字符,而题目输入本身已经是整数,字符数组只是为了方便访问首位和末位。
十进制首尾¶
整数的末位可以通过 x % 10 直接取得。首位可以先找到最大的十进制位权 divisor,再通过
x / divisor 取得。例如 x = 4554 时,divisor = 1000,首位和末位都为 4。
一对数字相等后,需要同时删除首位和末位:
x = x % divisor / 10。
x % divisor 删除首位,随后除以 10 删除末位。对应的位权也删除两位,因此执行
divisor /= 100。循环继续比较缩短后整数的首尾数字。
compareOuterDigits 删除了字符串和双指针,工作空间降为 O(1)。它仍需先扫描一次位数来确定
divisor,随后每轮处理一对数字。
直接完整反转整数也能与原值比较,但反转后的数学值可能超过 32 位范围,需要额外的溢出判断或更宽 类型。判断回文并不需要构造完整反转值,只需让原数的左右两半能够直接比较。
后一半反转¶
主解法从原数末尾逐位取数,并把取出的后缀反向累积到 reversedHalf:
reversedHalf = reversedHalf * 10 + x % 10。
随后执行 x /= 10,从原数中删除刚才取出的末位。每轮之后:
x保存尚未移动的原数字前缀;reversedHalf保存已移动后缀的逆序;两者共同覆盖原数的全部十进制位。
当 reversedHalf 达到或超过 x 时,右侧已经移动了至少一半数字,继续反转不会产生新的镜像
信息,因此循环条件写成 x > reversedHalf。
快速排除¶
负数可以立即返回 false,因为负号只出现在十进制表示开头。
非零且末位为 0 的整数也可以立即排除。若它是回文数,首位必须同样为 0,但正常整数表示
没有前导零。条件必须保留 x != 0,因为数字 0 本身是回文数。
这个末位零检查还有一个实现作用:进入半反转循环的正数末位一定非零,因此 reversedHalf 第一次
加入数字后不会因前导零丢失位数,两个状态可以可靠地通过数值大小定位中点。
奇偶比较¶
偶数位整数在中点停止时,两边长度相同。原数为回文,当且仅当未移动前缀等于后缀逆序:
x == reversedHalf。
奇数位整数中,reversedHalf 会比 x 多保存一个中间数字。中间数字不需要与任何位置配对,
删除它后再比较:
x == reversedHalf / 10。
两个条件合并为 x == reversedHalf || x == reversedHalf / 10,不需要预先计算整数位数。
状态推演¶
以 x = 12321 为例:
轮次 |
更新前 |
取出位 |
更新后 |
|
|---|---|---|---|---|
1 |
12321 |
1 |
1232 |
1 |
2 |
1232 |
2 |
123 |
12 |
3 |
123 |
3 |
12 |
123 |
此时 x > reversedHalf 不再成立。reversedHalf 的个位 3 是中间数字,删除后得到
123 / 10 = 12,与剩余前缀 12 相等。
对于 x = 4554,两轮后得到 x = 45、reversedHalf = 45,直接满足偶数位比较。
代码演进¶
compareAsString 把整数转换为可随机访问的字符序列,再使用左右指针比较镜像位置。代码简单,
但增加了字符串存储。
compareOuterDigits 使用除法和取模直接读取整数首尾数字,字符串和字符指针消失;代码增加
divisor,用于定位当前首位并在每轮删除两端数字。
reverseSecondHalf 不再寻找首位,也不再维护十进制位权。它只从末尾取数,直到反转部分覆盖一半,
随后直接比较两半。位数预扫描、首位提取和完整数字反转都被删除。
公开入口采用 reverseSecondHalf。它只处理约一半数字,使用常数状态,并从结构上避免完整反转值
可能产生的溢出。
复杂度分析¶
方法 |
时间复杂度 |
工作空间 |
主要状态 |
|---|---|---|---|
字符串双指针 |
|
|
十进制字符串与两个边界 |
十进制首尾比较 |
|
|
当前整数与最高位权 |
后一半反转 |
|
|
剩余前缀与反转后缀 |
d 是整数的十进制位数。半反转只执行约 d / 2 轮,但渐进时间仍记为 O(d)。
边界处理¶
所有负数在进入数字处理前返回
false;0绕过非零末位零检查,循环不执行,最终通过偶数形式比较返回true;非零末位零直接返回
false,避免丢失反转部分的前导零;单个正数位经过一轮后满足
x == reversedHalf / 10,返回true;半反转最多保存约一半数字,不会构造完整的 32 位反转结果。