[leetcode]Palindrome Number

新博文地址：[leetcode]Palindrome Number

http://oj.leetcode.com/problems/palindrome-number/

 

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.

 

写道

Hint:
Don’t be deceived by this problem which seemed easy to solve. Also note the restriction of doing it without extra space. Think of a generic solution that is not language/platform specific. Also, consider cases where your solution might go wrong.

Solution:
First, the problem statement did not specify if negative integers qualify as palindromes. Does negative integer such as -1 qualify as a palindrome? Finding out the full requirements of a problem before coding is what every programmer must do. Here, we define negative integers as non-palindromes.

The most intuitive approach is to first represent the integer as a string, since it is more convenient to manipulate. Although this certainly does work, it violates the restriction of not using extra space. (ie, you have to allocate n characters to store the reversed integer as string, where n is the maximum number of digits). I know, this sound like an unreasonable requirement (since it uses so little space), but don’t most interview problems have such requirements?

Another approach is to first reverse the number. If the number is the same as its reversed, then it must be a palindrome.This seemed to work too, but did you consider the possibility that the reversed number might overflow?

We could construct a better and more generic solution. One pointer is that, we must start comparing the digits somewhere. And you know there could only be two ways, either expand from the middle or compare from the two ends. 

no more extra space?我还以为一点的空间都不能有呢，木想到还是有o(1)个空间的。看了提示之后，算法自然就想到了：（不过还是人家的代码好看。。。。贴出来晒晒）

	public boolean isPalindrome(int x) {
		if(x < 0){
			return false;
		}
		int divisor = 1;
		//为了得到最高位的数字，要选择合适的除数
		while(x / divisor >= 10){
			divisor *= 10;
		}
		while(x != 0){
			int high = x/divisor;
			int low = x%10;
			if(high != low){
				return false;
			}
			x = (x - high * divisor) / 10;
			divisor /= 100;
		}
		return true;	
	}