【LeetCode】0009. Palindrome Number

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


Example 1:

1
2
Input: 121
Output: true

Example 2:

1
2
3
4
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:

1
2
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?


Related Topics: Math



解題邏輯與實作

既然是判斷回文,那麼直覺作法就是比頭尾是否相同,如果轉字串實做會變得很簡單,所以我就直接做 Follow up 要求了。


取尾數比較常見使用 mod (%) 即可。但取最高數的頭則比較麻煩,以 20001 為例,想取出最高位數,則必須計算 20001 // 10000 ,而除數 10000,其實可以換成這樣表示 $10^{len(被除數)-1}$ 。但另一個問題是,被除數是 int 沒有 len 這個函數,因此實際計算時改用迴圈計算被除數除以 10 直到小於 10 的次數,即為 len(被除數)-1 的值。

最後比較結束後,會將比較數字(e.g. 20001)去頭尾,並將除數(10000)除以 100 ,因為這個除數是對應比較數字長度,我將比較數字去頭尾,因此除數也必須至少有兩位數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
   def isPalindrome(self, x: int) -> bool:
      if (x < 0) | ((x % 10 == 0 ) & (x != 0)):
         return False

      div = 1
      while x // div >= 10:
         div *= 10

      while x > 0:
         highest = x // div
         lowest = x % 10

         if highest != lowest:
            return False

         x = (x % div) // 10
         div /= 100

      return True		


一開始的判斷是判斷兩種 case:

  1. 是否為負數,若是負數則不可能是回文
  2. 判斷尾數使否為 0,因為最高位數不可為 0 ,因此若尾數為 0 則不可能是回文,當然必須排除掉 0 本身。



除比頭尾外,另一個想法是翻轉後兩數直接相比,個人推測這種方法的效能應該會比較好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
   def isPalindrome(self, x: int) -> bool:
      if (x < 0) | ((x % 10 == 0 ) & (x != 0)):
         return False

      reverse_x = self.reverse(x)
      return x == reverse_x

   def reverse(self, x: int) -> int:
      res = 0;
      while x != 0:
         res = res * 10 + x % 10;
         x //= 10;

      return res


果然效能好很很多,從 88 ms/60.57 % 提升到 56 ms/ 99.10%



其他連結

  1. 【LeetCode】0000. 解題目錄