回文数判断：算法实现与优化技巧

丁香医生

1. 回文数问题概述

回文数判断是算法学习中的经典入门题目，也是各大技术面试中的高频考点。所谓回文数，是指正序和倒序读都相同的数字，例如121、1331等。这个问题看似简单，却蕴含着算法设计中关于效率优化和边界条件处理的重要思想。

在实际编程中，我们经常会遇到需要验证输入数据合法性的场景。比如在开发一个会员系统时，可能需要检查用户输入的身份证号、银行卡号等数字是否符合特定规则。回文数判断就是这类基础验证的典型代表。

2. 解题思路分析

2.1 问题拆解

判断一个整数是否为回文数，核心在于比较数字的正序和逆序表示。根据这个基本思路，我们可以衍生出三种主要解法：

字符串转换法：将数字转为字符串后比较
完全反转法：将数字整体反转后比较
半反转法：只反转数字的后半部分进行比较

每种方法都有其适用场景和优缺点，我们需要深入理解它们的实现细节和性能特征。

2.2 边界条件考虑

无论采用哪种方法，都需要特别注意以下边界情况：

负数永远不是回文数（如-121）
个位数为0的非零数不是回文数（如10、100）
0是回文数
大数情况下的溢出问题

3. 字符串转换法实现

3.1 实现原理

字符串法是最直观的解决方案，其核心思想是将整数转换为字符串后，使用双指针技术从两端向中间比较字符是否相同。

c复制#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool isPalindrome(int x) {
    if (x < 0) return false;
    
    char str[20];
    sprintf(str, "%d", x);
    
    int left = 0;
    int right = strlen(str) - 1;
    
    while (left < right) {
        if (str[left] != str[right]) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

3.2 复杂度分析

时间复杂度：O(n)，其中n是数字的位数。需要遍历整个字符串。
空间复杂度：O(n)，需要额外的字符串存储空间。

提示：虽然这种方法代码简单易懂，但在C语言中需要处理字符串转换，且空间效率不高，通常不是最优解。

4. 完全数字反转法

4.1 实现原理

这种方法通过数学运算将数字完全反转，然后比较反转前后的数值是否相等。

c复制#include <stdbool.h>

bool isPalindrome(int x) {
    if (x < 0) return false;
    
    long reverse = 0;
    int temp = x;
    
    while (temp != 0) {
        reverse = reverse * 10 + temp % 10;
        temp /= 10;
    }
    
    return reverse == x;
}

4.2 关键点说明

使用long类型存储反转结果，防止int溢出
通过取模(%)和除法(/)操作逐位反转数字
保留原始x的值，在临时变量temp上进行操作

4.3 复杂度分析

时间复杂度：O(log n)，因为数字位数是log10(n)
空间复杂度：O(1)，只使用了固定数量的变量

注意事项：虽然这种方法空间效率高，但对于极大整数(如2147483647)，反转后可能导致溢出，即使使用long类型也存在风险。

5. 反转一半数字法（最优解）

5.1 算法思想

这是LeetCode官方推荐的最优解法，核心思想是只反转数字的后半部分，然后与前半部分比较。这种方法巧妙地避免了完全反转可能导致的溢出问题。

5.2 实现细节

c复制#include <stdbool.h>

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;
}

5.3 关键步骤解析

预处理排除：
- 所有负数都不是回文数
- 末尾为0的非零数不是回文数
反转过程：
- 每次取出x的最后一位加到reversed的末尾
- 同时将x除以10（相当于去掉最后一位）
- 当x ≤ reversed时停止，此时已经反转了一半或过半的数字
最终比较：
- 数字长度为偶数：x == reversed
- 数字长度为奇数：x == reversed / 10（去掉中间数字）

5.4 示例演示

以x=12321为例：

初始：x=12321, reversed=0
第一次：x=1232, reversed=1
第二次：x=123, reversed=12
第三次：x=12, reversed=123
停止循环(x ≤ reversed)
比较：12 == 123/10 → true

5.5 复杂度分析

时间复杂度：O(log n)，只反转了一半数字
空间复杂度：O(1)，仅使用常数空间

6. 方法对比与选择建议

方法	时间复杂度	空间复杂度	优点	缺点
字符串法	O(n)	O(n)	实现简单	需要额外空间
完全反转	O(log n)	O(1)	空间效率高	可能溢出
半反转法	O(log n)	O(1)	最优效率	逻辑稍复杂