AI & Data Dreamers練功房
寶箱片場規則
ALGO GATES・演算法關卡・初階・3 題

演算法初階・堆疊與佇列

後進先出與先進先出:撤銷指令、路徑正規化、最近時間窗的呼叫數。

這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。

  1. 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 執行,只用標準函式庫。

    作答登入後可作答
  2. 02

    物件儲存路徑正規化

    容易堆疊

    資料湖的設定檔裡,物件路徑常被寫成 /raw/./stock/../price//2024 這種樣子。寫入前要正規化成標準形式。規則:

    • 以 / 切開,空的片段與 . 直接忽略
    • .. 代表回到上一層;已經在最上層(/)時忽略
    • 其他片段是資料夾名稱
    • 結果以 / 開頭、各層以單一 / 連接、結尾不加 /;什麼都不剩時是 /

    輸入:

    第 1 行:路徑數 n

    接下來 n 行:每行一個以 / 開頭的路徑

    輸出:n 行,依輸入順序印出每個路徑正規化後的結果。

    範例輸入:

    2

    /raw/./etl/../stock

    /tmp/..

    範例輸出:

    /raw/stock

    /

    類型對應:LeetCode「Simplify Path」類(情境與敘述為本平台改寫)。

    輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。

    作答登入後可作答
  3. 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 執行,只用標準函式庫。

    作答登入後可作答