演算法初階・堆疊與佇列
後進先出與先進先出:撤銷指令、路徑正規化、最近時間窗的呼叫數。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 01
資料修補指令撤銷
容易堆疊補資料的工具接受兩種指令,依序執行:
ADD x:把讀數 x(整數)加進結果的最後面UNDO:撤銷最近一次還留在結果裡的 ADD(也就是移除結果的最後一筆);結果是空的時候這個 UNDO 不做任何事
輸入:
第 1 行:指令數 n
接下來 n 行:每行一個指令
輸出:兩行
第 1 行:全部執行完後結果裡的讀數,依加入順序以空白分隔;結果是空的印
EMPTY第 2 行:結果裡讀數的總和(空的時候是 0)
範例輸入:
4
ADD 5
ADD 9
UNDO
ADD 2
範例輸出:
5 2
7
類型對應:LeetCode「Baseball Game」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 02
物件儲存路徑正規化
容易堆疊資料湖的設定檔裡,物件路徑常被寫成
/raw/./stock/../price//2024這種樣子。寫入前要正規化成標準形式。規則:- 以
/切開,空的片段與.直接忽略 ..代表回到上一層;已經在最上層(/)時忽略- 其他片段是資料夾名稱
- 結果以
/開頭、各層以單一/連接、結尾不加/;什麼都不剩時是/
輸入:
第 1 行:路徑數 n
接下來 n 行:每行一個以
/開頭的路徑輸出:n 行,依輸入順序印出每個路徑正規化後的結果。
範例輸入:
2
/raw/./etl/../stock
/tmp/..
範例輸出:
/raw/stock
/
類型對應:LeetCode「Simplify Path」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 以
- 03
最近 w 秒的 API 呼叫數
容易佇列API 閘道要即時顯示「最近 w 秒內的呼叫數」。每收到一次呼叫(時間戳 t 秒),就計算時間落在 t-w 到 t(含兩端)的呼叫有幾次,包含這一次。
輸入:
第 1 行:w
第 2 行:呼叫的時間戳(整數,以空白分隔,嚴格遞增)
輸出:一行,每次呼叫當下算出的次數,依呼叫順序以空白分隔。
要求:用 collections.deque 當佇列:新呼叫從右邊放進去,太舊的從左邊移出,不要每次都回頭數整份清單。
範例輸入:
5
1 2 6 7 12
範例輸出:
1 2 3 3 2
類型對應:LeetCode「Number of Recent Calls」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答

送件鴿飛出去了