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 位反转结果。