0009. Palindrome Number
=======================
题目信息
--------
:题号: 0009. 回文数
:难度: Easy
:主题: 数学、整数、回文
:原题: `LeetCode 0009 `_
:重点: 从字符串镜像比较,推导到直接处理十进制首尾数字,再用半反转删除位数统计与完整反转
题目重述
--------
给定一个 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++ 实现
--------
.. code-block:: cpp
#include
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(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`` 为例:
.. list-table::
:header-rows: 1
* - 轮次
- 更新前 ``x``
- 取出位
- 更新后 ``x``
- ``reversedHalf``
* - 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``。它只处理约一半数字,使用常数状态,并从结构上避免完整反转值
可能产生的溢出。
复杂度分析
~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 工作空间
- 主要状态
* - 字符串双指针
- ``O(d)``
- ``O(d)``
- 十进制字符串与两个边界
* - 十进制首尾比较
- ``O(d)``
- ``O(1)``
- 当前整数与最高位权
* - 后一半反转
- ``O(d)``
- ``O(1)``
- 剩余前缀与反转后缀
``d`` 是整数的十进制位数。半反转只执行约 ``d / 2`` 轮,但渐进时间仍记为 ``O(d)``。
边界处理
~~~~~~~~
* 所有负数在进入数字处理前返回 ``false``;
* ``0`` 绕过非零末位零检查,循环不执行,最终通过偶数形式比较返回 ``true``;
* 非零末位零直接返回 ``false``,避免丢失反转部分的前导零;
* 单个正数位经过一轮后满足 ``x == reversedHalf / 10``,返回 ``true``;
* 半反转最多保存约一半数字,不会构造完整的 32 位反转结果。