🚩 前言

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

1.题目描述

原题链接：NC56 回文数字
描述
在不使用额外的内存空间的条件下判断一个整数是否是回文。
回文指逆序和正序完全相同。
数据范围：

−

2

31

≤

n

≤

2

31

−

1

-2^{31} \le n \le 2^{31}-1

$- 2^{31} \leq n \leq 2^{31} - 1$
进阶：空间复杂度

O

(

1

)

O(1)

$O (1)$ ，时间复杂度

O

(

l

e

n

(

n

)

)

O(len(n))

$O (l e n (n))$
提示：
负整数可以是回文吗？（比如 – 1）
如果你在考虑将数字转化为字符串的话，请注意一下不能使用额外空间的限制
你可以将整数翻转。但是，如果你做过题目“反转数字”，你会知道将整数翻转可能会出现溢出的情况，你怎么处理这个问题？

2.算法设计思路

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

如何反转一个整数呢？参见：【牛客-算法】NC57 反转数字

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