題目：

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

click to show spoilers.

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.

鏈接：?http://leetcode.com/problems/palindrome-number/

題解：

可以用除法和模運(yùn)算rebuild一個(gè)結(jié)果，然后比較和輸入是否相等。這里其實(shí)有可能會(huì)overflow，就是在 result * 10的時(shí)候，但越界的話也會(huì)返回一個(gè)32位整數(shù)，這個(gè)整數(shù)是 result * 10結(jié)果轉(zhuǎn)換為64位里面的low 32位，一般來說與輸入不同。所以結(jié)果返回false，也能過AC，但是不嚴(yán)謹(jǐn)。

Time Complexity - O(logx)， Space Complexity - O(1)。

public class Solution {public boolean isPalindrome(int x) {if(x == 0)return true;int result = 0, temp = x; while(temp > 0){result = 10 * result + temp % 10;temp /= 10;}return result == x;} }

?

另外一種方法可以避免overflow。先用對(duì)數(shù)計(jì)算出x有幾位，然后通過數(shù)學(xué)運(yùn)算比較第一位和最后一位是否相等，接下來去掉最大的一位和最小的一位，再將digitNum - 2，繼續(xù)進(jìn)行計(jì)算。

Time Complexity - O(logx)， Space Complexity - O(1)。

public class Solution {public boolean isPalindrome(int x) {if(x < 0)return false;int digitNum= (int)(Math.log(x) / Math.log(10)); int left = 0, right = 0;while(x > 0){int powInTens = (int)Math.pow(10, digitNum);left = x / powInTens;right = x % 10;if(left != right)return false;x -= left * powInTens;x /= 10;digitNum -= 2 ;}return true;} }

?

二刷：

Java: - Reverse all digits:

public class Solution {public boolean isPalindrome(int x) {if (x < 0) {return false;}int res = 0, tmp = x;while (tmp > 0) {res = res * 10 + tmp % 10;tmp /= 10;}return res == x;} }

Reverse half digits:

public class Solution {public boolean isPalindrome(int x) {if (x < 0 || (x != 0 && x % 10 == 0)) {return false;}int res = 0;while (x > res) {res = res * 10 + x % 10;x /= 10;}return (res == x) || (x == res / 10);} }

?

Python:

class Solution(object):def isPalindrome(self, x):""":type x: int:rtype: bool"""if x < 0 or (x != 0 and x % 10 == 0):return Falseres = 0while x > res:res = res * 10 + x % 10x /= 10return (x == res) or (x == res / 10)

?

三刷:

Java:

計(jì)算全部digits: ?設(shè)立一個(gè)int n = x， 然后我們計(jì)算一下n的按位反轉(zhuǎn)數(shù)res，最后比較 n == res

public class Solution {public boolean isPalindrome(int x) {if(x < 0) {return false;}int n = x;int res = 0;while (x > 0) {res = res * 10 + x % 10;x /= 10;}return res == n;} }

?

計(jì)算一半digits:

這里我們要先剪掉特殊情況 x % 10 == 0，這時(shí)候假如x不為0的話，肯定不是palindromic number。

之后while循環(huán)作比較的條件是 ?x ?> res。 我們只需要計(jì)算一半的digits，然后比較是否 x == res， 或者 x == res / 10。

當(dāng)x是偶數(shù)長度的話，我們比較 x == res; 當(dāng)x時(shí)奇數(shù)長度的時(shí)候，比如 x = 1，這時(shí)我們比較的是 x == res / 10。合起來用一個(gè)或運(yùn)算就可以了。

public class Solution {public boolean isPalindrome(int x) {if(x < 0 || (x != 0 && x % 10 == 0)) {return false;}int res = 0;while (x > res) {res = res * 10 + x % 10;x /= 10;}return (x == res || x == res / 10) ;} }

?

?

?

Reference:

https://leetcode.com/discuss/33500/an-easy-lines-code-only-reversing-till-half-and-then-compare

https://leetcode.com/discuss/23563/line-accepted-java-code-without-the-need-handling-overflow

https://leetcode.com/discuss/12693/neat-ac-java-code-o-n-time-complexity?

https://leetcode.com/discuss/65915/python-solution-with-other-variable-introduced-besides-input

?

轉(zhuǎn)載于:https://www.cnblogs.com/yrbbest/p/4430410.html

總結(jié)

以上是生活随笔為你收集整理的9. Palindrome Number的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。