Menu
    1. 2025-03-05-判断回文数
    2. 取反对比
    3. 左右翻转
    4. 双指针

    2025-03-05-判断回文数

    post on 05 Mar 2025 about 1643words require 6min
    CC BY 4.0 （除特别声明或转载文章外）
    如果这篇博客帮助到你，可以请我喝一杯咖啡~

    2025-03-05-判断回文数

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

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

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

    取反对比

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

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

    左右翻转

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

    1
2
3
4
5
6
7
8
9
10
11
12
13

    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 个数字(输入为偶数个数字)时结束。

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

    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. 考虑偶数位的回文数：假设我们有一个有偶数位的回文数 $N $，设其位数为 $2k$ （其中 $k$是正整数）。我们可以将 $N $ 表示为：
    \[N = a_1a_2 \ldots a_ka_{k+1} \ldots a_{2k}\]

    其中 $a_1 = a_{2k}， a_2 = a_{2k-1}，\ldots， a_k = a_{k+1}$ 。

    1. 将回文数表示为数学形式：我们可以将 $N$ 写成：
    \[N = a_1 \cdot 10^{2k-1} + a_2 \cdot 10^{2k-2} + \cdots + a_k \cdot 10^k + a_k \cdot 10^{k-1} + \cdots + a_2 \cdot 10 + a_1\]

    这可以重写为：

    \[N = a_1 (10^{2k-1} + 1) + a_2 (10^{2k-2} + 10) + \cdots + a_k (10^k + 10^{k-1})\]
    1. 提取公因数：注意到每一项 $10^{2i-1} + 10^{2i-2}$ 都可以提取公因数 $10^{i-1}$ ：
    \[N = a_1 (10^{2k-1} + 1) + a_2 \cdot 10 (10^{2k-3} + 1) + \cdots + a_k \cdot 10^{k-1} (10 + 1)\]

    这可以进一步简化为：

    \[N = \textcolor{blue}{[}a_1 (10^{2k-1} + 1) + a_2 \cdot 10 (10^{2k-3} + 1)\textcolor{blue}{]} + \cdots + a_k \cdot 10^{k-1} \cdot 11\]
    1. 分离公因数 11：由于 $10 + 1 = 11$ ，我们可以看到 $N$ 可以被11整除。因此，$N$ 有一个因子 11。
    2. 结论：因为 $N$ 有因子 11，所以 $N$ 不是质数，除非 $N = 11 $。但是题目中已经排除了 11 的情况。 因此，有偶数位的回文数（除了 11）必然不是质数。
    Loading comments...