题目
判断一个整数是否为回文数。不能申请其他的空间。
解答思路
在解决该题前，得先明白什么是回文数，即“回文”是指正读反读都是同一个数。
本题的难点在于不能申请额外的空间，即，要求空间复杂度为 O(1) 。
我们很容易想到一个解决方案，就是通过逆序解决，但是有个问题，就是逆序的时候，这个整数有可能会出现溢出，而且不能申请额外的空间。所以，这个思路行不通。
我有一种思路：利用时间换空间。
由于不能申请额外的空间，所以，就只能通过时间去换空间。可以用嵌套循环解决该问题，即，如果len为该整数的长度，则第一层循环为每次取整数的第i位，i=1,..,len/2-1，第二层循环为取元素的第len-i+1个元素。然后判断这两个元素是否相等即可。
下面则是该思路的Java程序：
public boolean isPalindrome(int x) { if(x < 0) return false; int len = 1; while(Math.pow(10,len) <= x){ len++; } int subx1 = x; int temp = (int)Math.pow(10,len-1); for(int i = 0;i < len/2;i++){ int begin = subx1 / temp;// 取首位元素 subx1 = subx1 % temp; temp = temp / 10; int subx2 = x; int temp1 = (int)Math.pow(10,len-1); int end = 0; for(int j = i;j < len;j++){ // 取对应的末尾元素 end = subx2 / temp1; subx2 = subx2 % temp1; temp1 = temp1 / 10; } if(begin != end) return false; } return true; }由程序可以看出，该算法的时间复杂度最大为 O(n2/2) ，空间复杂度为 O(1) 。
