🚩 前言

🔥 该专栏作为算法题笔记，记录算法的思路、遇到的问题，以及能跑的代码，持续更新中！ 🔥 推荐一款面试、刷题神器牛客网：👉👈

1.题目描述

原题链接： 描述 在不使用额外的内存空间的条件下判断一个整数是否是回文。 回文指逆序和正序完全相同。 数据范围： − 2 31 ≤ n ≤ 2 31 − 1 -2^{31} le n le 2^{31}-1 −231≤n≤231−1 进阶： 空间复杂度 O ( 1 ) O(1) O(1)，时间复杂度 O ( l e n ( n ) ) O(len(n)) O(len(n)) 提示： 负整数可以是回文吗？（比如 - 1） 如果你在考虑将数字转化为字符串的话，请注意一下不能使用额外空间的限制 你可以将整数翻转。但是，如果你做过题目“反转数字”，你会知道将整数翻转可能会出现溢出的情况，你怎么处理这个问题？

2.算法设计思路

if（数字是负数） 不回文 else if（反转后的数字与原数字相等） 回文

如何反转一个整数呢？参见：

3.算法实现（C语言）

#include<limits.h>


int reverse(int x ) {
          
   
    //反转数字，对于超出范围的情况，将返回0
    if(x == INT_MIN)//INT_MIN取相反数运算，数将不变
    {
          
   
        return 0;
    }

    int t = x;//备份

    bool big = false;//x的数量级是否为10亿
    if(x > 1000000000)
    {
          
   
        big = true;
    }
    
    int f = 1;//f数量级指向首位，e数量级指向末位；将向中间迭代
    int e = 1;
    while(x / f / 10 > 0) //得到x首位的数量级
    {
          
   
        f *= 10;
    }

    while(f > e)
    {
          
   
        int fNum = x / f % 10;//得到首、末位数字
        int eNum = x / e % 10;
        x = x - f * fNum + f * eNum;//交换数字
        x = x - e * eNum + e * fNum;
        f /= 10;//向中间迭代
        e *= 10;
    }

    int eNum = t % 10;
    if(big && (eNum > 2 || (eNum != 0 && x < 1000000000)))//反转后溢出
    {
          
   
        return 0;
    }

    return x;
}

bool isPalindrome(int x ) {
          
   
    //是否回文
    bool result = false;
    if(x >= 0){
          
   
        int x2 = reverse(x);
        if(x == x2){
          
   
            result = true;
        }
    }
    return result;
}

4.运行结果

🧭 结束语：

今天的分享就到这里啦，快来一起刷题叭！ 👉👈

完