首頁 > 軟體

Python雙端佇列實現迴文檢測

2022-01-14 19:01:08

一、雙端佇列

雙端佇列 Deque 是一種有次序的資料集,跟佇列相似,其兩端可以稱作"首" 和 "尾"端,但 Deque 中資料項既可以從隊首加入,也可以從隊尾加入;資料項也可以從兩端移除。某種意義上說,雙端佇列整合了棧和佇列的能力。

但雙端佇列並不具有內在的 LIFO 或者 FIFO 特性,如果用雙端佇列來模擬棧或佇列,需要由使用者自行維護操作的一致性。

用 Python 實現抽象資料型別Deque,Deque定義的操作如下:

  • Deque():建立一個空雙端佇列;
  • add_front(item):將 item 加入隊首;
  • add_tail(item):將 item 加入隊尾;
  • remove_front():從隊首移除資料項,返回值為移除的資料項;
  • remove_tail():從隊尾移除資料項,返回值為移除的資料項;
  • is_empty():返回 Deque 是否為空;
  • get_size():返回 Deque 中包含資料項的個數。

定義雙端佇列,程式碼實現如下:

class Deque:
    def __init__(self):   # 建立空的雙端佇列
        self.items = []

    def is_empty(self):   # 判斷雙端佇列是否為空
        return self.items == []

    def add_front(self, item):   # 從隊首加入元素 
        self.items.append(item)

    def add_tail(self, item):    # 從隊尾加入元素 
        self.items.insert(0, item)

    def remove_front(self):      # 從隊首刪除元素 
        if self.is_empty():
            raise Exception('Queue is empty')
        return self.items.pop()

    def remove_tail(self):       # 從隊尾刪除元素 
        if self.is_empty():
            raise Exception('Queue is empty')
        return self.items.pop(0)

    def get_size(self):          # 獲取雙端佇列元素數量
        return len(self.items)

操作複雜度:add_front / remove_front,O(1);add_tail / remove_tail,O(n)。

二、迴文檢測

“迴文詞” 指正讀和反讀都一樣的詞,如radar、bob、toot;中文:“上海自來水來自海上”,“山東落花生花落東山”。

用雙端佇列很容易解決 “迴文詞” 問題,先將需要判定的詞從隊尾加入Deque,再從兩端同時移除字元判定是否相同,直到 Deque 中剩下 0 個或 1 個字元。

演演算法實現如下:

def palindrome_check(string):   # 迴文檢測
    str_deque = Deque()
    for item in string:
        str_deque.add_front(item)
        
    check_flag = True
    while str_deque.get_size() > 1 and check_flag:
        left = str_deque.remove_front()   # 隊尾移除
        right = str_deque.remove_tail()   # 隊首移除
        if left != right:   # 只要有一次不相等   不是迴文
            check_flag = False
    # 判斷完一遍   check_flag為True  是迴文
    return check_flag

print(palindrome_check("radar"))
print(palindrome_check("abcbac"))
print(palindrome_check("上海自來水來自海上"))

補充

Python還可以通過雙遊標判斷字串是否是迴文串

從字串s兩端指定兩個遊標low,high

如果low遊標指向了 非字母和數位(即空格和符號),那麼low遊標往後移一位;

如果high遊標指向了 非字母和數位(即空格和符號),那麼high遊標往前移一位;

直至low和high都指向了數位或字母,此時進行比較,是否相同。

如果比較的結果是True,則low往後移一位,high往前移一位

如果比較的結果是False,則直接返回False

重複上述判斷,直至low和high重合,此時表示完成了字串s內前後元素的一一對比判斷,返回True即可。

程式碼如下

class Solution(object):
  def isPalindrome(self, s):
    """
    :type s: str
    :rtype: bool
    """
    low = 0
    high = len(s) - 1
    #在字串為空或只有一個字元時,返回True
    if len(s) <= 1:
      return True
    # 設定low和high對比的條件
    while low < high:
     # 如果不是字母或數位,low往後移一位【low < high為必須條件,不然會造成索引越界】
      while not s[low].isalnum() and low < high:
        low += 1
      # 如果不是字母或數位,high往前移一位
      while not s[high].isalnum() and low < high:
        high -= 1
       # 判斷:如果相同,繼續下一次對比;如果不相同,直接返回False
      if s[low].lower() == s[high].lower():
        low += 1
        high -= 1
      else:
        return False
    # low和high重合,即退出迴圈,表示前後都是一一對應的,返回True
   return True

到此這篇關於Python雙端佇列實現迴文檢測的文章就介紹到這了,更多相關Python迴文檢測內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com!


IT145.com E-mail:sddin#qq.com