🚩 前言
🔥 该专栏作为算法题笔记，记录算法的思路、遇到的问题，以及能跑的代码，持续更新中！
1.题目描述
- 原题链接：NC56 回文数字
- 描述
在不使用额外的内存空间的条件下判断一个整数是否是回文。
回文指逆序和正序完全相同。
提示：
负整数可以是回文吗？（比如 - 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; }
4.运行结果
🧭 结束语：
今天的分享就到这里啦，快来一起刷题叭！
