LeetCode回文数问题C++解法报错：部分测试用例未通过

原代码 #

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) {
            return false;
        }
        if(x < 10){
          return true;
        }
        int s = 0;
        int en = floor(log10(x));
        while(s < en){
          if(x % 10 != ((x / int(pow(10, en))))) {
              return false;
          }
          x = (x % int(pow(10, en))) / 10;
          s++;
          en--;
        }
        return true;
    }
};

问题描述 #

这段代码用于判断整数是否为回文数，多数测试用例可通过，但在9999、11211、112211这类用例中返回false，无法通过。代码思路是通过s（起始标识）和en（末尾标识）从整数两端向中间遍历，逐一比对首尾数字，期望达到O(n/2)的时间复杂度。

错误原因 #

问题出在浮点数运算的精度误差：

• log10和pow都是浮点数函数，计算结果可能存在精度偏差。例如计算pow(10,3)时，实际得到的可能是999.9999999，强制转换为int后会变成999，而非预期的1000。
• 以9999为例：en初始值为floor(log10(9999))=3，int(pow(10,3))变成999，此时x/999=10，而x%10=9，两者不相等，直接返回false，导致误判。

修复方案 #

方案一：用整数运算替代浮点数函数 #

完全避免浮点数精度问题，通过循环计算数字位数和10的幂次：

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        if (x < 10) return true;

        // 计算数字的总位数对应的10的幂次
        int temp = x;
        int power = 1;
        while (temp >= 10) {
            temp /= 10;
            power *= 10;
        }

        int s = 0;
        int en = log10(power); // 这里用log10没问题，因为power是10的整数次幂
        while (s < en) {
            int first = x / power;
            int last = x % 10;
            if (first != last) return false;

            // 去掉首尾两位数字
            x = (x % power) / 10;
            power /= 100; // 每次去掉两位，幂次除以100
            s++;
            en--;
        }
        return true;
    }
};

方案二：反转后半部分数字对比（更简洁高效） #

直接反转数字的后半段，与前半段对比，完全规避浮点数问题：

class Solution {
public:
    bool isPalindrome(int x) {
        // 负数或末尾为0但本身非0的情况直接排除
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;

        int reversedHalf = 0;
        // 反转后半部分数字，直到原数小于等于反转后的数（说明已经处理了一半）
        while (x > reversedHalf) {
            reversedHalf = reversedHalf * 10 + x % 10;
            x /= 10;
        }

        // 偶数位时x等于reversedHalf；奇数位时x等于reversedHalf/10（去掉中间的数字）
        return x == reversedHalf || x == reversedHalf / 10;
    }
};

内容的提问来源于stack exchange，提问作者Anuj Garg