1.题目描述
Determine whether an integer is a palindrome. Do this without extra space.
Some hints:
Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.
2.我的分析思路
因为之前做过数字倒序输入的题目,所以我的想法就是算出他的倒序数字,然后进行对比。当然,从提示中我们可以看到,一些负数什么的,是不满足条件的。所以,我们将负数刨除在外。
简单的代码就不写了,结果就是写了之后,贴上去,结果编译不通过,郁闷。。应该还有其他的好的算法,哎,被虐的不要不要的。
3.其他的思路
看大家的讨论内容,思路有了一些拓展,看到了评论最多的一个方法,贴出来如下:
public static boolean isPalindrome(int x) throws Exception {
if (x < 0 || (x != 0 && x % 10 == 0)) return false;
int rev = 0;
while (x > rev) {
rev = rev * 10 + x % 10;
x = x / 10;
}
return (x == rev || x == rev / 10);
}
这个算法依旧很妙,沿用了之前数字倒序输出的思路,但是有了一些变化。中间这一段算法的目的就是求出这个数字的后几位数的倒序表示的数字。
比如,我们输入的数字是1221,我们经过中间的循环,算出的rev=12,x=12,也就是算出了后面两个数字21的倒序数,就是12,与前面的12相等,符合x==rev的条件,输出true。还有一种情况就是数字的位数为奇数位,此时求出的rev是(位数/2+1)取整的倒序数字,比如数组12321,此时rev=123,x=12,满足条件x==rev/10的条件,同样的也能得到true。
看了讨论,真是让我汗颜啊~~~