LeetCode Palindrome Number

LeetCode 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.


这一题很有意思,要我们判断一个整数是否是回文数。

首先负数不是回文数,个位数是回文数。但是怎样判断大于9的整数是否是回文数呢?

首先想到的是把int转换为string表示,这样就很方便判断了,但是题目要求不能用额外的存储空间,也就是不能用和x位数线性以上的存储空间,当然几个常数空间是可以的。

后来想依次取出数字的首尾数字,判断是否相等。但是中间有0出现时会有问题,比如1000021,去掉首尾1之后只剩int x=2了,导致判断错误。

还有一个办法是将x转换为x的逆序x',然后依次判断x和x'的末尾是否相等,但是x'可能超出int表示范围,又作罢。

后来观察发现,回文数字765567在转换为逆序数的过程中,肯定有某个状态,x==x',比如765=765,而这时x'肯定不会超出int的表示范围。所以我们可以在边逆序的时候边判断。

完整代码如下:

class Solution {
public:
	bool isPalindrome(int x) {
		if (x < 10)
			return x >= 0;
		if (x % 10 == 0)
			return false;
		int y = 0;
		while (x > y)
		{
			y = y * 10 + x % 10;
			if (x == y) //76567
				return true;
			x /= 10;
			if (x == y) //765567
				return true;
		}
		return false;
	}
};

本代码提交AC,用时76MS。

Leave a Reply

Your email address will not be published. Required fields are marked *