LeetCode 騰訊精選練習50——009 回文數

LeetCode 009 回文數

Author：

Labyrinthine Leo

   Init_time：

2021.01.13

Index Words：

LeetCode 009

公衆号：

Leo的部落格城堡

題目

• 回文數
• 題号：009
• 難度：簡單
• https://leetcode-cn.com/problems/palindrome-number/

判斷一個整數是否是回文數。回文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數。

示例 1

:

輸入: 121
輸出: true
           

示例 2

:

輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 。 從右向左讀, 為 121- 。是以它不是一個回文數。
           

示例 3

:

輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 。是以它不是一個回文數。
           

進階

:

你能不将整數轉為字元串來解決這個問題嗎？

Python實作

1、按位取值比較

思路：将數值按位提取添加到清單中，然後使用雙指針首尾周遊清單，進行判斷是否相同即可判斷回文與否。

時間複雜度：

O(n)

空間複雜度：

O(n)

• 狀态：通過
• 執行用時: 76 ms, 在所有 python3 送出中擊敗了 66% 的使用者
• 記憶體消耗: 14.7 MB, 在所有 python3 送出中擊敗了 26.92% 的使用者

# coding  : utf-8
# fun     : Leetcode 009 回文數
# @Author : Labyrinthine Leo
# @Time   : 2021.01.13

class Solution:
    def isPalindrome(self, x: int) -> bool:
    	if x < 0:
    		return False
 
    	reverse_list = [] # 将數值各位轉為清單存儲
    	while x > 0:
    		reverse_list.append(x%10)
    		x //=10
    	# print(reverse_list)
    	l, r = 0, len(reverse_list)-1
    	while l < r: # 首尾雙指針比較
    		if reverse_list[l] != reverse_list[r]:
    			return False
    		l += 1
    		r -= 1
    	return True

# 測試樣例
x = 121
s = Solution()
print(s.isPalindrome(x))
           

2、轉為字元串對比

思路：同上，隻是直接轉為字元串進行首尾對稱比較，更加友善。

• 狀态：通過
• 執行用時: 64 ms, 在所有 python3 送出中擊敗了 92.83% 的使用者
• 記憶體消耗: 15 MB, 在所有 python3 送出中擊敗了 5.42% 的使用者

# 字元串求解
class Solution:
    def isPalindrome(self, x: int) -> bool:
    	s = str(x)
    	l = len(s)
    	h = l // 2
    	return s[:h] == s[-1:-h-1:-1] # 順序i+逆序j = -1, 0+-1=-1

# 測試樣例
x = -121
s = Solution()
print(s.isPalindrome(x))
           

tips

• 對于字元串首尾對稱判斷：

  s[:h] == s[-1:-h-1:-1]

  (h為字元串中間位置索引)