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

演算法中階・樹的走訪

父子清單建樹:逐層走訪、深度優先找路徑成本、沿父指標找最近共同祖先。

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

  1. 01

    設定版本樹逐層列出

    中等樹

    設定檔的每個版本都從某個父版本衍生出來,形成一棵樹(只有一個根版本)。檔案以「版本 父版本」逐行記錄,根版本的父版本寫 -。請從根開始一層一層列出所有版本,並找出版本最多的那一層。

    同一個父版本底下的子版本,依它們在輸入中出現的先後排列;每一層依「上一層的順序,再依各自子版本的順序」排列。

    輸入:

    第 1 行:組數 t

    每組:第 1 行是版本數 n,接下來 n 行是 版本 父版本

    輸出:每組

    • 每一層一行:深度: 版本 版本 ...(根的深度是 0,深度與冒號之間沒有空白,冒號後一個空白)
    • 最後一行:widest 深度 個數,個數相同時取深度較小的

    要求:先建「父版本 → 子版本 list」的 dict,再用佇列一層一層走(每輪把目前這一層全部處理完再進下一層)。

    範例輸入:

    1

    4

    b a

    a -

    c a

    d b

    範例輸出:

    0: a

    1: b c

    2: d

    widest 1 2

    類型對應:LeetCode「N-ary Tree Level Order Traversal」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答
  2. 02

    血緣路徑成本剛好等於預算

    中等樹

    資料血緣是一棵樹:根是原始資料的匯入步驟,每往下一層是一個處理步驟,每個步驟有處理成本。從根走到某個葉節點(沒有子節點的步驟)就是一條完整產出的路徑,路徑成本是路上所有步驟(含根與葉)的成本總和。給幾個預算值,列出成本剛好等於預算的所有路徑。

    同一個父步驟底下的子步驟,依它們在輸入中出現的先後排列;路徑依「從根開始深度優先、先走前面的子步驟」的順序列出。

    輸入:

    第 1 行:步驟數 n

    接下來 n 行:步驟 父步驟 成本(根的父步驟寫 -,成本是非負整數;父步驟可能在子步驟之後才出現)

    最後一行:預算值(整數,以空白分隔,至少一個)

    輸出:每個預算依輸入順序

    • 先印一行 預算 k,k 是符合的路徑數
    • 接下來 k 行,每行一條路徑,步驟以 > 連接

    要求:用深度優先走訪,一路帶著目前的路徑與累計成本,走到葉節點才判斷;不要先把所有路徑存起來。

    範例輸入:

    4

    load - 1

    a load 2

    b load 3

    c a 1

    4 3

    範例輸出:

    4 2

    load > a > c

    load > b

    3 0

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

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

    作答登入後可作答
  3. 03

    兩個設定版本的共同祖先

    中等樹

    設定檔的版本樹裡,每個版本記著它的父版本(根版本的父版本寫 -)。合併兩個分支前,要找出兩個版本最近的共同祖先:同時是兩者祖先、而且離它們最近的版本。一個版本也算是自己的祖先。

    輸入:

    第 1 行:版本數 n

    接下來 n 行:版本 父版本

    下一行:查詢數 q

    接下來 q 行:版本a 版本b

    輸出:每個查詢一行 共同祖先 a往上幾步 b往上幾步(步數是從該版本沿父版本往上走到共同祖先的次數)。

    要求:用父版本指標往上走,不需要建子節點清單。

    範例輸入:

    4

    r -

    a r

    b r

    c a

    2

    c b

    a c

    範例輸出:

    r 2 1

    a 0 1

    類型對應:LeetCode「Lowest Common Ancestor of a Binary Tree III」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答