- 回文数字 2023-08-18 美团 一面
在不使用额外的内存空间的条件下判断一个整数是否是回文。
回文指逆序和正序完全相同。
数据范围：
进阶： 空间复杂度O(1) ，时间复杂度 O(n)
提示：
负整数可以是回文吗？（比如-1）
如果你在考虑将数字转化为字符串的话，请注意一下不能使用额外空间的限制
你可以将整数翻转。但是，如果你做过题目“反转数字”，你会知道将整数翻转可能会出现溢出的情况，你怎么处理这个问题？
public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param x int整型 * @return bool布尔型*///1. 负整数在这道题里不算是回文，比如-121!=121-//方案一：121%10=1,121/100=1public boolean isPalindrome (int x) {
// if (x<0) return false;
// String str = x + "";
// int len = str.length();
// if (len==1){
// return true;
// }// int mid = len/2;
// int p=0;
// for (int i=1;i<=mid;i++){
// int temp = x%10;
// System.out.println("temp="+temp);
// p=p*10 + temp;
// x = x/10;
// }
// if (x == p){
// return true;
// }
// return false;int y = 0;int a = x;while (a>0){y = y * 10 + (a%10);a = a/10;}return y == x;}
}
上面的被注释的代码才是本人所写，当然，一开始说需要O(logn)的时间复杂度，所以想到要二分，求得了x的位数长度。然后是判断负数是否是回文，题目认为不是，所以有了判断为负就直接返回false；所以整体写的略微复杂了。后面的结果是面试官给出的答案，是比较美观、简洁的代码，思路很清晰。
当然，这道题其实有几个特点：首先他不是回文字符串，而是数字，数字类问题意味着我们可以做加减乘除、位运算等，也就是说我们没必要转成字符串然后判断回文，可以利用数字的特性通过多次取模乘10这样来反转数字。所以这是这道算法题希望考察到的点。
