C++实现回文数判断的两种高效算法

1. 回文数问题概述

回文数是指正序（从左向右）和倒序（从右向左）读都相同的整数。例如121是回文数，而123不是。这个问题看似简单，但在实际编程面试和算法练习中经常出现，主要考察程序员对数字操作、边界条件处理以及算法效率的理解。

在C++中解决这个问题，我们需要考虑几个关键点：负数处理、数字反转的边界条件、以及如何高效地进行数字反转。负数显然不可能是回文数（因为负号的存在），所以可以直接排除。对于正数，我们需要将其反转并与原数比较，如果相同则是回文数。

2. 解决方案设计思路

2.1 基本解法：数字反转比较

最直观的解法是将数字完全反转，然后与原数字比较。这种方法简单直接，但需要注意反转过程中可能出现的整数溢出问题。在C++中，int类型通常是32位，最大值为2147483647，当反转一个接近这个值的数字时，可能会导致溢出。

cpp复制bool isPalindrome(int x) {
    if (x < 0) return false;
    long long reversed = 0;
    int original = x;
    while (x != 0) {
        reversed = reversed * 10 + x % 10;
        x /= 10;
    }
    return reversed == original;
}

这个解法使用了long long类型来存储反转后的数字，避免了溢出问题。时间复杂度是O(log10(n))，因为我们需要处理数字的每一位。

2.2 优化解法：反转一半数字

更高效的解法是只反转数字的一半，然后与剩下的部分比较。这种方法不仅减少了计算量，还完全避免了溢出问题。

cpp复制bool isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }
    
    int reversed = 0;
    while (x > reversed) {
        reversed = reversed * 10 + x % 10;
        x /= 10;
    }
    
    return x == reversed || x == reversed / 10;
}

这个解法的关键在于循环条件x > reversed，当原始数字小于或等于反转后的数字时，说明我们已经处理了一半以上的数字。对于偶数位数字，x和reversed会相等；对于奇数位数字，x会等于reversed/10（中间数字不影响回文性质）。

3. 边界条件与特殊处理

3.1 负数处理

负数由于有负号的存在，显然不可能是回文数。因此，我们可以直接返回false：

cpp复制if (x < 0) return false;

3.2 末尾为0的数字

除了0本身，任何以0结尾的数字都不可能是回文数，因为数字的最高位不可能是0。我们可以添加这个检查：

cpp复制if (x % 10 == 0 && x != 0) {
    return false;
}