題目
第9題：回文數(shù)
判斷一個整數(shù)是否是回文數(shù)。回文數(shù)是指正序（從左向右）和倒序(從右向左)讀都是一樣的整數(shù)忘闻。
示例 1:
輸入: 121
輸出: true
示例 2:
輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 精续。 從右向左讀, 為 121- 。因此它不是一個回文數(shù)处窥。
示例 3:
輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 。因此它不是一個回文數(shù)损搬。
進階:
你能不將整數(shù)轉(zhuǎn)為字符串來解決這個問題嗎碧库？
思路&實現(xiàn)
思路：先取出各個數(shù)字變成list柜与，再翻轉(zhuǎn)；然后判斷新的list與原來的是否一致
class Solution:
def isPalindrome(self, x):
"""
先取出各個數(shù)字組成list嵌灰，再翻轉(zhuǎn)
:type x: int
:rtype: bool
"""
li = []
if x < 0:
return False
else:
while x != 0:
li.append(x % 10)
x = int(x / 10)
return list(reversed(li)) == li
官方解釋
首先弄匕，我們應(yīng)該處理一些臨界情況。所有負數(shù)都不可能是回文沽瞭，例如：-123 不是回文迁匠，因為 - 不等于 3。所以我們可以對所有負數(shù)返回 false驹溃。
現(xiàn)在城丧，讓我們來考慮如何反轉(zhuǎn)后半部分的數(shù)字。 對于數(shù)字 1221豌鹤，如果執(zhí)行 1221 % 10亡哄，我們將得到最后一位數(shù)字 1，要得到倒數(shù)第二位數(shù)字布疙，
我們可以先通過除以 10 把最后一位數(shù)字從 1221 中移除蚊惯，1221 / 10 = 122，再求出上一步結(jié)果除以10的余數(shù)灵临，122 % 10 = 2截型，
就可以得到倒數(shù)第二位數(shù)字。
如果我們把最后一位數(shù)字乘以10儒溉，再加上倒數(shù)第二位數(shù)字宦焦，1 * 10 + 2 = 12，
就得到了我們想要的反轉(zhuǎn)后的數(shù)字顿涣。 如果繼續(xù)這個過程波闹，我們將得到更多位數(shù)的反轉(zhuǎn)數(shù)字。
現(xiàn)在的問題是园骆，我們?nèi)绾沃婪崔D(zhuǎn)數(shù)字的位數(shù)已經(jīng)達到原始數(shù)字位數(shù)的一半舔痪？
我們將原始數(shù)字除以 10，然后給反轉(zhuǎn)后的數(shù)字乘上 10锌唾，所以锄码，當原始數(shù)字小于反轉(zhuǎn)后的數(shù)字時，就意味著我們已經(jīng)處理了一半位數(shù)的數(shù)字晌涕。
復(fù)雜度分析
時間復(fù)雜度：O(\log_{10}(n))O(log 10 (n))滋捶， 對于每次迭代，我們會將輸入除以10余黎，因此時間復(fù)雜度為 O(\log_{10}(n))O(log10(n))重窟。
空間復(fù)雜度：O(1)O(1)。
實現(xiàn)
根據(jù)官方的解釋惧财，我試著實現(xiàn)了一下：
def gaunfang(self, x):
'''
用時：400ms
:param x:
:return:
'''
if x < 0:
return False
temp_x = x
y = 0
while temp_x != 0:
y = y * 10 + temp_x % 10
temp_x = int(temp_x / 10)
return y == x
其他方法
def reversed_str(self, x):
'''
翻轉(zhuǎn)字符串
用時：446ms
:param x:
:return:
'''
if str(x) == str(x)[::-1]:
return True
else:
return False
這個方法主要是采用了字符串截取的方法巡扇，從最后逐位翻轉(zhuǎn)扭仁，在判斷。
題目難度
難度：簡單
總結(jié)
這道題的算法難度不大厅翔，實現(xiàn)起來簡單乖坠，但是沒有想到的是，python的實現(xiàn)方法會是如此的簡潔刀闷⌒鼙茫看來，還是的多接觸一下優(yōu)秀的代碼甸昏，增長一下自己的見識才行Ｍ绶帧７坠搿对途！
