[LeetCode-我在失敗的路上-Part 4] 9. Palindrome Number

6 min readFeb 7, 2020

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

這次為了避免前面的錯誤，還特別紀錄重點，並先確認好題目重點，自己記錄了：

檢查是否回文
不可轉成 String

根據題目規則，我想出了 Coding 要點：

判斷負號
判斷長度，並利用 Dict 儲存每位元的數字
迭代 Dict 判斷是否相同

第一版：

class Solution:
    def isPalindrome(self, x: int) -> bool:
        
        sign = [1, -1][x < 0]
        if sign == -1:
            return False
        
        D, c = {}, 0
        while x != 0:
            D[c] = x % 10
            x //= 10
            c += 1for i in range( c ):
            if D[i] == D[c - i - 1]:
                return True
        return False

結果訝異的錯誤，結果 Input 為 0 的時候失敗，於是

第二版：

class Solution:
    def isPalindrome(self, x: int) -> bool:
        
        sign = [1, -1][x < 0]
        if sign == -1:
            return False
        if x == 0:
            return True
        
        D, c = {}, 0
        while x != 0:
            D[c] = x % 10
            x //= 10
            c += 1for i in range( c ):
            if D[i] == D[c - i - 1]:
                return True
        return False

記憶體限制? 我在卡了一陣子，都是程式碼小修改

終於被我發現問題點，這時候已經

第八版：

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x == 0:
            return True
        if x < 0:
            return FalseD, c = {}, 0
        while x != 0:
            D[c] = x % 10
            x //= 10
            c += 1for i in range( c ):
            if D[i] != D[c - i - 1]:
                return False
        return True

總結：

Runtime 實在太差，運用太多的變數。如果要改善效能需要利用數學運算。

向其他人學習，來自 https://leetcode.com/tc639 提出兩個方案：

Method 1：

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        
        p, res = x, 0
        while p:
            res = res * 10 + p % 10
            p //= 10
        return res == x

Method 1 分析：

負數都為 False
利用 res * 10 進一位、 p % 10 取最後一位，達到數字反轉效果
利用 p//= 10 將數字最後一位去除
重複 2、3 步驟，值到 p 為 0 時結束

Method 2：

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        b = 1
        while x // b >= 10:
            b *= 10
        while b >= 10:
            if x // b != x % 10:
                return False
            x, b = (x % b) // 10, b // 100
        return True

Method 2 分析：

負數都為 False
計算 x 的數位
假設 x // b (頭) 與 x % 10 (尾) 不相同時， return False
x = x % b (去頭)
x = x // 10 (去尾)
b = b // 100 (減少數位，頭尾兩個位數)
重複 2 ~ 6步驟，直到 b 低於十位數

顯然這個效率，可能沒辦法認同，筆者調查高效率的程式碼是這樣的：

class Solution:
    def isPalindrome(self, x: int) -> bool:
        return str(x) == str(x)[::-1]

沒錯，沒看錯! 就是轉換成字串，並利用切片(Slice) 的作法。其他高效率都是利用字串。說到這我就想說題目不是說不能用嗎? 我又看了一次。

Follow up:

Coud you solve it without converting the integer to a string?

恐怕這個意思只是看我們能不能不使用整數轉字串的方式解決，並沒有硬性規定阿!

[LeetCode-我在失敗的路上-Part 4] 9. Palindrome Number

Written by PoHan Lin