Python雙端隊列實現(xiàn)回文檢測
一、雙端隊列
雙端隊列 Deque 是一種有次序的數(shù)據(jù)集,跟隊列相似,其兩端可以稱作"首" 和 "尾"端,但 Deque 中數(shù)據(jù)項既可以從隊首加入,也可以從隊尾加入;數(shù)據(jù)項也可以從兩端移除。某種意義上說,雙端隊列集成了棧和隊列的能力。
但雙端隊列并不具有內在的 LIFO 或者 FIFO 特性,如果用雙端隊列來模擬?;蜿犃?,需要由使用者自行維護操作的一致性。
用 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)
操作復雜度: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還可以通過雙游標判斷字符串是否是回文串
從字符串s兩端指定兩個游標low,high
如果low游標指向了 非字母和數(shù)字(即空格和符號),那么low游標往后移一位;
如果high游標指向了 非字母和數(shù)字(即空格和符號),那么high游標往前移一位;
直至low和high都指向了數(shù)字或字母,此時進行比較,是否相同。
如果比較的結果是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: # 如果不是字母或數(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),表示前后都是一一對應的,返回True return True
到此這篇關于Python雙端隊列實現(xiàn)回文檢測的文章就介紹到這了,更多相關Python回文檢測內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
python網(wǎng)絡爬蟲實現(xiàn)發(fā)送短信驗證碼的方法
這篇文章主要介紹了python網(wǎng)絡爬蟲實現(xiàn)發(fā)送短信驗證碼的方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2021-02-02python利用pandas和csv包向一個csv文件寫入或追加數(shù)據(jù)
這篇文章主要給大家介紹了關于python利用pandas和csv包向一個csv文件寫入或追加數(shù)據(jù)的相關資料,我們越來越多的使用pandas進行數(shù)據(jù)處理,有時需要向一個已經(jīng)存在的csv文件寫入數(shù)據(jù),需要的朋友可以參考下2023-07-07Python設置Socket代理及實現(xiàn)遠程攝像頭控制的例子
這篇文章主要介紹了Python設置Socket代理及實現(xiàn)遠程攝像頭控制的例子,皆是對socket模塊的實際運用,需要的朋友可以參考下2015-11-11