这篇文章上次修改于 237 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

2025-03-05-判断回文数

参考博客
判断回文数算法
判断回文数(三种解法)—— Leetcode(9)_求回文数-CSDN 博客

回文数是指正序（从左到右）读和倒序（从右到左）读都是一样的整数。

比如形如 121，1221，13531 的数字都是回文数，但 -121，10，25 等等都不是回文数。

取反对比

一种容易想到的方法是：将整个数取反后看和原来的数是否相同。

bool isPalindrome(int x) {  
    if (x<0)  
        return false;  
    long long sum =0;  
    long long origin = x;  
    while(x)  
    {  
        int num = x %10;  
        sum = sum*10 + num;  
        x/=10;  
    }  
    if(sum == origin)  
        return true;  
    else  
        return false;  
}

左右翻转

根据回文数的特点，我们只需要判断左边一半和翻转后的右边一半是否相等即可。

bool isPalindrome(int x) {
    // 负数肯定不是，以及首尾不对称的非0数
    if(x < 0 || (x % 10 == 0 && x != 0))
        return false;

    int rev = 0;
    while ( x > rev){
        rev = rev * 10 + x % 10; //将低位一半的数取反。
        x = int (x / 10);
    }
    //有rev >= x， 奇数情况下需要除去10
    return x == rev || x == int(rev/10); 
}

双指针

在循环体中，不断地比较第 i 位和倒数第 i 位，直到遇到最中间的 1 个数字(输入为奇数个数字)或者遇到最中间的 2 个数字(输入为偶数个数字)时结束。

bool isPalindrome(int x) {  
  if (x < 0) return false;  
  int div = 1;  
  while (x / div >= 10) {  
    div *= 10;  
  }          
  while (x != 0) {  
    int l = x / div;  
    int r = x % 10;  
    if (l != r) return false;  
    x = (x % div) / 10;  //去掉两边的数
    div /= 100;  
  }  
  return true;  
}

补充:一个证明,有偶数位的回文数能被 11 整除

  1. 考虑偶数位的回文数：假设我们有一个有偶数位的回文数 ，设其位数为 （其中 是正整数）。我们可以将 表示为：

其中 ，，， 。

  1. 将回文数表示为数学形式：我们可以将 写成：

这可以重写为：

  1. 提取公因数：注意到每一项 都可以提取公因数 ：

这可以进一步简化为：

  1. 分离公因数 11：由于 ，我们可以看到 可以被11整除。因此， 有一个因子 11。
  2. 结论：因为 有因子 11，所以 不是质数，除非 。但是题目中已经排除了 11 的情况。
    因此，有偶数位的回文数（除了 11）必然不是质数。