0009. Palindrome Number

题目信息

题号:
  1. 回文数

难度:

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++ 实现

#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 为例:

轮次

更新前 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。它只处理约一半数字,使用常数状态,并从结构上避免完整反转值 可能产生的溢出。

复杂度分析

方法

时间复杂度

工作空间

主要状态

字符串双指针

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