Problem

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:

[code lang=”shell” collapse=”true”]
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.
[/code]

Ideas

原题注明不得使用额外的空间,所以放弃掉将数字转换成字符串的方式。

可以考虑将整形数字进行取反,但是取反后会有益处的情况。怎么办?既然是判断是否为回文数字,那么翻转一半的数字后,和未翻转的数字进行比对就可以了。这样就不会导致数字益处的问题了。

在反转时,如何判断已经反转到了中间的数字?如果未反转的数字大于已经反转的数字,那么此时就是中点(或者是和中点相差一位的位置)。

Code

[code lang=”cpp”]
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x > 0)) return false;
int r_x = 0;
while (x > r_x) {
r_x = r_x * 10 + (x % 10);
x /= 10;
}

return x == r_x || x == r_x / 10;
}
};
[/code]


文章来源:胡小旭 => [LeetCode]Palinkdrom Number

Share:

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.