欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python雙端隊(duì)列實(shí)現(xiàn)回文檢測

 更新時間:2022年01月14日 14:10:59   作者:葉庭云  
雙端隊(duì)列 Deque 是一種有次序的數(shù)據(jù)集,跟隊(duì)列相似,其兩端可以稱作"首" 和 "尾"端。這篇文章將通過雙端隊(duì)列實(shí)現(xiàn)回文檢測,感興趣的可以學(xué)習(xí)一下

一、雙端隊(duì)列

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

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

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

  • Deque():創(chuàng)建一個空雙端隊(duì)列;
  • add_front(item):將 item 加入隊(duì)首;
  • add_tail(item):將 item 加入隊(duì)尾;
  • remove_front():從隊(duì)首移除數(shù)據(jù)項(xiàng),返回值為移除的數(shù)據(jù)項(xiàng);
  • remove_tail():從隊(duì)尾移除數(shù)據(jù)項(xiàng),返回值為移除的數(shù)據(jù)項(xiàng);
  • is_empty():返回 Deque 是否為空;
  • get_size():返回 Deque 中包含數(shù)據(jù)項(xiàng)的個數(shù)。

定義雙端隊(duì)列,代碼實(shí)現(xiàn)如下:

class Deque:
? ? def __init__(self): ? # 創(chuàng)建空的雙端隊(duì)列
? ? ? ? self.items = []

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

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

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

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

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

? ? def get_size(self): ? ? ? ? ?# 獲取雙端隊(duì)列元素數(shù)量
? ? ? ? return len(self.items)

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

二、回文檢測

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

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

算法實(shí)現(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() ? # 隊(duì)尾移除
? ? ? ? right = str_deque.remove_tail() ? # 隊(duì)首移除
? ? ? ? if left != right: ? # 只要有一次不相等 ? 不是回文
? ? ? ? ? ? check_flag = False
? ? # 判斷完一遍 ? check_flag為True ?是回文
? ? return check_flag

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

補(bǔ)充

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

到此這篇關(guān)于Python雙端隊(duì)列實(shí)現(xiàn)回文檢測的文章就介紹到這了,更多相關(guān)Python回文檢測內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • python網(wǎng)絡(luò)爬蟲實(shí)現(xiàn)發(fā)送短信驗(yàn)證碼的方法

    python網(wǎng)絡(luò)爬蟲實(shí)現(xiàn)發(fā)送短信驗(yàn)證碼的方法

    這篇文章主要介紹了python網(wǎng)絡(luò)爬蟲實(shí)現(xiàn)發(fā)送短信驗(yàn)證碼的方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-02-02
  • 詳解MindSpore自定義模型損失函數(shù)

    詳解MindSpore自定義模型損失函數(shù)

    在不同的訓(xùn)練場景中,我們時常需要使用不同的損失函數(shù)來衡量一個模型的計算結(jié)果的優(yōu)劣,本文重點(diǎn)介紹了在MindSpore中如何去自定義一個損失函數(shù)?;贛indSpore中的Loss類,我們可以通過繼承該類后,再重寫construct函數(shù)和get_loss函數(shù)實(shí)現(xiàn)全面自定義的損失函數(shù)形式與內(nèi)容
    2021-06-06
  • Django加載配置的過程詳解

    Django加載配置的過程詳解

    這篇文章主要介紹了Django加載配置的過程詳解,包括Django服務(wù)啟動 manage.py的詳細(xì)介紹,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-05-05
  • Python實(shí)現(xiàn)PS濾鏡的旋轉(zhuǎn)模糊功能示例

    Python實(shí)現(xiàn)PS濾鏡的旋轉(zhuǎn)模糊功能示例

    這篇文章主要介紹了Python實(shí)現(xiàn)PS濾鏡的旋轉(zhuǎn)模糊功能,涉及Python基于skimage庫針對圖片進(jìn)行旋轉(zhuǎn)與模糊化處理的相關(guān)操作技巧,需要的朋友可以參考下
    2018-01-01
  • 基于wxpython開發(fā)的簡單gui計算器實(shí)例

    基于wxpython開發(fā)的簡單gui計算器實(shí)例

    這篇文章主要介紹了基于wxpython開發(fā)的簡單gui計算器,實(shí)例分析了基于wxpython實(shí)現(xiàn)簡單桌面應(yīng)用程序的相關(guān)技巧,需要的朋友可以參考下
    2015-05-05
  • Python數(shù)組與列表的區(qū)別解析

    Python數(shù)組與列表的區(qū)別解析

    列表因?yàn)槠浯鎯Φ念愋涂梢允侨魏螌ο螅虼肆斜淼挠锰幐鼜V泛,更多樣化,并且列表可以有更多的存儲空間去使用,而數(shù)組使用的空間就相對較少,這篇文章主要介紹了Python數(shù)組與列表的區(qū)別,需要的朋友可以參考下
    2023-11-11
  • 置信橢圓原理以及橢圓圖形繪制方式

    置信橢圓原理以及橢圓圖形繪制方式

    這篇文章主要介紹了置信橢圓原理以及橢圓圖形繪制方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-02-02
  • python利用pandas和csv包向一個csv文件寫入或追加數(shù)據(jù)

    python利用pandas和csv包向一個csv文件寫入或追加數(shù)據(jù)

    這篇文章主要給大家介紹了關(guān)于python利用pandas和csv包向一個csv文件寫入或追加數(shù)據(jù)的相關(guān)資料,我們越來越多的使用pandas進(jìn)行數(shù)據(jù)處理,有時需要向一個已經(jīng)存在的csv文件寫入數(shù)據(jù),需要的朋友可以參考下
    2023-07-07
  • Python實(shí)現(xiàn)iOS自動化打包詳解步驟

    Python實(shí)現(xiàn)iOS自動化打包詳解步驟

    這篇文章主要介紹了Python實(shí)現(xiàn)iOS自動化打包詳解步驟,文中通過示例代碼以及圖文介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2018-10-10
  • Python設(shè)置Socket代理及實(shí)現(xiàn)遠(yuǎn)程攝像頭控制的例子

    Python設(shè)置Socket代理及實(shí)現(xiàn)遠(yuǎn)程攝像頭控制的例子

    這篇文章主要介紹了Python設(shè)置Socket代理及實(shí)現(xiàn)遠(yuǎn)程攝像頭控制的例子,皆是對socket模塊的實(shí)際運(yùn)用,需要的朋友可以參考下
    2015-11-11

最新評論