演算法高階・滑動視窗、字首樹與滾動雜湊
atMost 相減數區段、dict 字首樹做路由比對、二分搜尋加滾動雜湊找重複片段。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 01
剛好 k 個使用者的事件區段
困難滑動視窗事件串流依時間記錄了每一筆事件的 user_id。分析「多人同時互動」的片段時,要數有幾個連續區段(至少一筆)裡剛好有 k 個不同的 user_id。起點或終點不同就算不同的區段。
輸入:
第 1 行:組數 t
接下來 t 行:
k user_id...(以空白分隔),或GEN k n m seed(由 starter 產生 n 筆事件,user_id 是u1到um)。GEN開頭的行是大量測資的縮寫:starter 已寫好gen(),讀進來後跟一般的 list 一樣,不用自己處理。輸出:每組一行,剛好有 k 個不同 user_id 的區段數。
要求:用滑動視窗算「不同 user 數最多 k 個的區段數」,答案=atMost(k) − atMost(k−1),整體 O(n)。不要列舉每個起點往後掃(GEN 的資料有幾千筆)。
範例輸入:
2
2 a b a c
2 a a
範例輸出:
4
0
類型對應:LeetCode「Subarrays with K Different Integers」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 02
API 路由最長字首比對
困難字首樹API 閘道依路徑把請求轉給後端服務。路由規則以
/分段,段可以是固定字串或*(*剛好比對一個任意段)。一條規則比對到某個請求,是指規則的每一段依序跟請求路徑開頭的幾段相符(規則/沒有任何段,所以比對所有請求)。路徑前後多出來的/不影響分段,例如/api/v1/與/api/v1一樣。有多條規則比對得到時,依序比較:
- 段數多的優先
- 段數一樣時,從第一段往後逐段比,第一個不同的段是固定字串的那條優先(固定字串勝過
*)
輸入:
第 1 行:規則數 r
接下來 r 行:
路由 服務名(不會有兩條規則的分段完全相同)下一行:查詢數 q
接下來 q 行:請求路徑
輸出:每個查詢一行
請求路徑 服務名(請求路徑照輸入原樣印出);沒有規則比對得到印請求路徑 404。要求:用巢狀 dict 建字首樹,每個節點存子節點與(若有)服務名;查詢時沿著請求的段往下走,每一層同時試固定字串與
*兩個分支。不要對每個查詢逐條比對所有規則。範例輸入:
3
/api/v1 v1
/api/*/jobs jobs
/api/v1/jobs jobs-v1
3
/api/v1/jobs/7
/api/v9/jobs
/home
範例輸出:
/api/v1/jobs/7 jobs-v1
/api/v9/jobs jobs
/home 404
類型對應:LeetCode「Implement Trie (Prefix Tree)」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 03
事件代碼最長重複片段
困難滾動雜湊每個工作階段的事件被編成一個字母代碼串(例如
L是登入、V是瀏覽、C是加入購物車)。要找出整串中出現至少兩次的最長片段(連續的子字串),兩次出現可以重疊(例如AAAA的答案是AAA)。最長的片段有好幾個時,取「第一次出現的位置」最前面的那個。輸入:
第 1 行:組數 t
接下來 t 行:一個由大寫英文字母組成的代碼串,或
GEN n seed 字母表(由 starter 產生長度 n 的代碼串,每個字元取自字母表)。GEN開頭的行是大量測資的縮寫:starter 已寫好gen(),讀進來後跟一般的 list 一樣,不用自己處理。輸出:每組一行
長度 片段;沒有任何重複的字元時印NONE。要求:對長度做二分搜尋(長度 L 有重複,L−1 一定也有),檢查某個長度時用滾動雜湊在 O(n) 內算出所有長度 L 片段的雜湊值;雜湊相同要再比對字串,避免碰撞誤判。不要列舉所有片段兩兩比較。
範例輸入:
2
LVCLVCX
ABAB
範例輸出:
3 LVC
2 AB
類型對應:LeetCode「Longest Duplicate Substring」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答

送件鴿飛出去了