iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 23
0
Software Development

從零開始學Python系列 第 23

[Day 23] 從零開始學Python - 資料結構模組deque:旁人來來去去像行雲流水

  • 分享至 

  • xImage
  •  

註:本文同步刊載在Medium,若習慣Medium的話亦可去那邊看呦!

先來解一下上次的練習吧!
我們唯一需要動的應該只有calculate的函式,
當 p1 < p2 時,將兩個值交換即可。
別忘了交換應該要連同Entry裡面的值都一起換(price1/price2)。

### calculate函式用來接受按鈕事件,取得商品價格及折扣方式,計算後輸出
def calculate():
    # 每次要計算時,都讓按鈕顯示計算哪一個折扣法
    btnstr.set('計算' + radiostr.get() + '中')
    # 用try...except...的方式來避免掉輸入的不是數字
    try:
        choice = radiostr.get() # radiobutton的選擇項
        p1 = int(price1.get())
        p2 = int(price2.get())
        if p1 <= 0 or p2 <= 0: # 如果輸入<=0的數字也當成例外處理
            raise Exception()
        if p1 < p2:
            p1, p2 = p2, p1
            price1.set(str(p1))
            price2.set(str(p2))
...(下面沒有變動XD)

我們今天要來談談deque的應用,
我們前面已經在第十一篇的部分提到過deque的用法,這篇主要要來補充deque作為queue時的常見狀況。

一般我們提到兩種資料結構:
queue(佇列)或stack(堆疊)的概念,
其實就是先進先出(FIFO, First-In-First-Out)或先進後出(First-In-Last-Out)的區別。

queue就好像排隊一樣,當然是先排的先被服務到(除非有人插隊XD);
stack則像是一疊文件一樣,假設你都拿最上面的,
當老闆又往上放新的文件(工作)給你的時候,
你再拿就會拿到最新放上去的囉!
這兩者在不同的程式語言有時候會有不同的稱呼和變形,
但本質是不變的。

那麼,什麼狀況下我們寫程式會容易用到queue(deque)呢?
最常見的狀況是遇到一個Tree(樹)的問題的時候!
那,什麼是樹呢?
好問題!這個問題應該要用比較長的篇幅解釋,
所以請讀者參閱拙作從LeetCode學演算法的第十四篇
下面我們再繼續。

不囉嗦,我們直接上一道題目作為範例吧!
上面的連結應該已經介紹過二元樹了,
最簡單來說,一棵二元樹就是由根節點(root),
及左子樹(left tree)/右子樹(right tree)所構成。
每個節點上有可能連結左右節點,
也可能沒有連接,稱為NIL,在Python為None。
如果我們今天想要按照一層一層順序來走遍整個樹,
並分層記錄的話,該怎麼做呢?
這個問題通常被稱為Level-order Traversal。(層序遍歷)
讀者可以前往LeetCode的題目看更詳細的描述。
https://leetcode.com/problems/binary-tree-level-order-traversal/
我們可以先走第一層,再走第二層,以此類推,
那麼這中間走完第一層時,怎麼知道第二層有哪些節點呢?
按順序的話,我們應該將第一層的每個節點的左節點/右節點,
放入到一個可以按照放入的順序處理的資料結構,
接著再從這個資料結構裡一個一個拿出來(這時候是第二層了!),
找每一個的左右節點,再放進去......
咦?這個資料結構不就是queue嗎XD?

我們在解題和寫程式的時候,
可以先把要怎麼做大略寫出來,
再根據這個概念和做法,寫出具體的程式。

以這個問題來說,
題目應該會給出這個二元樹的根節點root,
接著要做的事情就如上面說的一樣,但我們需要一些細部的東西:

  1. 開一個res(result)作為存放答案用的串列。
  2. 我們先檢查root是否存在,有些題目壞壞的會給None,
    如果不存在就直接回傳空的答案給它!
  3. 將root放入我們檢查的資料結構(因為它是第一層),我們先叫它q吧!
  4. 開始一個迴圈,當q裡面還有節點時,代表還要繼續。
  5. 我們先記下q裡面的個數(命名為cnt),後面放進去q的都是下一層的節點。
  6. 接著先設定一個level變數,用以記錄這層的節點值們。
  7. 在裡面再開一個迴圈,這次直接指定跑cnt次,
    這樣所有這層的節點都會被我們取出來。
  8. 內層迴圈中,每次從q取出一個節點(popleft),
    將節點值(.value)append到level中,
  9. 檢查左節點,如果不是None的話就將節點放到q裡。
  10. 檢查右節點,做相同的事情XD
  11. 內層迴圈結束後,這時候我們拿到一整層的節點值,
    我們應該要將其append到res這個結果裡。
  12. 最後全部處理完後,可以將res回傳。

好啦!經過上面的步驟,有沒有發現我們其實已經把程式寫完了呢?
只要按著順序對照,應該可以順利寫出答案。

那麼,我們就來看看實際的做法:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import deque

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = [] # result,用以記錄結果
        if not root: return res # 我們有提過,if not可以用來檢查東西是不是空的
        q = deque([root]) # deque的初始化,要以list的形式放入
        while q: # 當q還有節點(同樣這相當於檢查是不是空的)
            cnt = len(q) # deque支援len的操作(取長度)
            level = [] # 記錄每層的節點值
            for _ in range(cnt): # _沒有特別意思,通常是當沒有要在迴圈內用到時可以使用
                n = q.popleft() # popleft等於從deque的左邊取出,也就是queue的用法
                level.append(n.val) # 取值
                if n.left: q.append(n.left) # 將左節點放入q
                if n.right: q.append(n.right) # 將右節點放入q
            res.append(level) # 每層完成後,要將一整層的節點值list放到res中
        
        return res # 回傳,結束!

應該不算太難(吧)...?
請務必要看完樹的那篇定義再來看這篇喲!
總言之,deque作為queue使用時,主要會用popleft()跟append()來操作,
同時它會適合按先後順序放入及取出的情況。

練習題目的話,
讀者可以再嘗試看看LeetCode的另一題:
101. Symmetric Tree

那麼,我們就明天見囉!


上一篇
[Day 22] 從零開始學Python - 圖形化使用者介面Tkinter:直到現在,我還默默的等待
下一篇
[Day 24] 從零開始學Python - 資料結構模組heapq:除了前幾名以外,在座的各位都是垃圾
系列文
從零開始學Python30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言