Palindrome Number
2016-06-20 本文已影响18人
violinmeng
Determine whether an integer is a palindrome. Do this without extra space.
判定一个整数是不是回文的，不要使用额外的临时空间。
解：
需要想到的几点：负数是不是回文如-1，如果想要转化为字符串，用字符串的倒置函数，要想到不能使用额外的临时空间。你也可以倒置这个数，但是要考虑数字有可能溢出，如果这个数溢出的话，必然不是回文数了，因为回文数的倒置之后的数等于原来的数。
采用这种思路：例如1234321利用取余和除数可以得到两个数1234和123或者另一种情况123321得到两个数123和123,进而判断是不是回文数，参考代码如下(C++)：
class Solution { public: bool isPalindrome(int x) { if(x<0) return false; if(x<10) return true; if(x%10==0) return false; if(x<100&&x%11==0) return true; if(x<1000&&((x/100)*10+x%10)%11==0) return true; int res = 0; while(x>res){ res = res*10 + x%10; x = x/10; } return (x==res || x==res/10); } };
时间复杂度为O(n),空间复杂度为O(1).
