基本概念

回文数是指正读和反读都相同的数字，例如121、1331、12321等。非回文数包括123、-121、10等。

算法方法对比

方法一：字符串反转法

bool isPalindrome(int n) {
    string str = to_string(n);
    string reversed = str;
    reverse(reversed.begin(), reversed.end());
    return str == reversed;
}

特点：简单直观，但需要额外字符串空间，效率相对较低。

方法二：完整数字反转法

bool isPalindrome(int n) {
    if (n < 0) return false;
    
    long long reversed = 0;
    int original = n;
    
    while (n > 0) {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }
    return original == reversed;
}

特点：纯数学运算，不需要字符串，但可能整数溢出。

方法三：双指针法

bool isPalindrome(int n) {
    string str = to_string(n);
    int left = 0, right = str.length() - 1;
    
    while (left < right) {
        if (str[left++] != str[right--]) 
            return false;
    }
    return true;
}

特点：只需比较到中间即可，但仍需字符串转换。

方法四：反转一半数字法（推荐）

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

算法原理分析（方法四）

反转一半数字法是最优解决方案，原因如下：

1. 时间复杂度为O(log₁₀n)
2. 空间复杂度为O(1)
3. 不会发生整数溢出问题
4. 无需额外数据结构
5. 执行效率最高

算法处理流程：

1. 边界条件检查：负数直接返回false，末尾为0的非零数返回false
2. 数字反转过程：只反转数字的一半
3. 奇偶位数处理：
   • 偶数位：直接比较 n == reversed
   • 奇数位：比较 n == reversed / 10（去掉中间位）

示例说明：

• 输入1221：n=12, reversed=12 → true
• 输入12321：n=12, reversed=123 → n == reversed/12 → true

性能比较

方法四在时间和空间复杂度上都是最优的，特别适合处理大规模数据。

使用建议

1. 日常使用和编程竞赛推荐使用方法四
2. 教学演示可以使用方法一，因为它最直观
3. 面试时需要掌握方法四并能解释其原理

注意事项

1. 所有方法都应先检查负数情况
2. 注意边界情况：0是回文数，个位数都是回文数
3. 以0结尾的数字（除0外）都不是回文数

总结

反转一半数字法是最优解决方案，它避免了整数溢出问题，空间复杂度为常数级，时间复杂度最优，适用于各种规模的输入。掌握这种方法的原理和实现对于算法学习具有重要意义。