Python雙端隊列怎么實現(xiàn)回文檢測

本文小編為大家詳細(xì)介紹“Python雙端隊列怎么實現(xiàn)回文檢測”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“Python雙端隊列怎么實現(xiàn)回文檢測”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識吧。

一、雙端隊列

雙端隊列 Deque 是一種有次序的數(shù)據(jù)集，跟隊列相似，其兩端可以稱作"首" 和 "尾"端，但 Deque 中數(shù)據(jù)項既可以從隊首加入，也可以從隊尾加入；數(shù)據(jù)項也可以從兩端移除。某種意義上說，雙端隊列集成了棧和隊列的能力。

但雙端隊列并不具有內(nèi)在的 LIFO 或者 FIFO 特性，如果用雙端隊列來模擬棧或隊列，需要由使用者自行維護(hù)操作的一致性。

用 Python 實現(xiàn)抽象數(shù)據(jù)類型Deque，Deque定義的操作如下：

• Deque()：創(chuàng)建一個空雙端隊列；

• add_front(item)：將 item 加入隊首；

• add_tail(item)：將 item 加入隊尾；

• remove_front()：從隊首移除數(shù)據(jù)項，返回值為移除的數(shù)據(jù)項；

• remove_tail()：從隊尾移除數(shù)據(jù)項，返回值為移除的數(shù)據(jù)項；

• is_empty()：返回 Deque 是否為空；

• get_size()：返回 Deque 中包含數(shù)據(jù)項的個數(shù)。

定義雙端隊列，代碼實現(xiàn)如下：

class Deque:
    def __init__(self):   # 創(chuàng)建空的雙端隊列
        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):          # 獲取雙端隊列元素數(shù)量
        return len(self.items)

操作復(fù)雜度：add_front / remove_front，O(1)；add_tail / remove_tail，O(n)。

二、回文檢測

“回文詞” 指正讀和反讀都一樣的詞，如radar、bob、toot；中文：“上海自來水來自海上”，“山東落花生花落東山”。

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

算法實現(xiàn)如下：

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還可以通過雙游標(biāo)判斷字符串是否是回文串

從字符串s兩端指定兩個游標(biāo)low，high

如果low游標(biāo)指向了 非字母和數(shù)字（即空格和符號）,那么low游標(biāo)往后移一位；

如果high游標(biāo)指向了 非字母和數(shù)字（即空格和符號）,那么high游標(biāo)往前移一位；

直至low和high都指向了數(shù)字或字母，此時進(jìn)行比較，是否相同。

如果比較的結(jié)果是True，則low往后移一位，high往前移一位

如果比較的結(jié)果是False，則直接返回False

重復(fù)上述判斷，直至low和high重合，此時表示完成了字符串s內(nèi)前后元素的一一對比判斷，返回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
    # 設(shè)定low和high對比的條件
    while low < high:
     # 如果不是字母或數(shù)字，low往后移一位【low < high為必須條件，不然會造成索引越界】
      while not s[low].isalnum() and low < high:
        low += 1
      # 如果不是字母或數(shù)字，high往前移一位
      while not s[high].isalnum() and low < high:
        high -= 1
       # 判斷：如果相同，繼續(xù)下一次對比；如果不相同，直接返回False
      if s[low].lower() == s[high].lower():
        low += 1
        high -= 1
      else:
        return False
    # low和high重合，即退出循環(huán)，表示前后都是一一對應(yīng)的，返回True
   return True

讀到這里，這篇“Python雙端隊列怎么實現(xiàn)回文檢測”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領(lǐng)會，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。