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

演算法初階・字串的基本操作

逐字元比對找共同前綴、字母計數比較配額、連續長度編碼壓縮狀態字串。

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

  1. 01

    物件路徑共同前綴

    容易字串

    資料湖的物件路徑(例如 s3://lake/raw/2024-01/orders.csv)常要找出一批路徑的共同前綴,用來決定一次列出哪個資料夾。請找出每一批路徑「從第一個字元開始、所有路徑都相同」的最長字串。比較以字元為單位,不管 / 的位置。

    輸入:

    第 1 行:批數 t

    接下來 t 行:每行一批路徑,以空白分隔,至少一條(路徑本身不含空白)

    輸出:每批一行,印出最長共同前綴;沒有任何共同字元時印 NONE。

    要求:先拿第一條路徑當候選前綴,逐條比對、不符就從尾端縮短。

    範例輸入:

    2

    raw/a.csv raw/b.csv

    x/1 y/1

    範例輸出:

    raw/

    NONE

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

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

    作答登入後可作答
  2. 02

    叢集資源配額檢查

    容易字元計數

    叢集的資源以字母表示一個單位:C 是一顆 CPU、G 是一張 GPU、M 是一單位記憶體(也可能出現其他大寫字母代表其他資源)。工作的需求寫成字串,例如 CCGM 表示要 2 顆 CPU、1 張 GPU、1 單位記憶體;節點目前可用的資源也寫成字串。每個單位只能分給一個需求。請判斷每份需求能不能由節點的可用資源滿足。

    輸入:

    第 1 行:組數 t

    接下來 t 行:需求 可用(兩個大寫字母字串,以空白分隔);節點沒有任何可用資源時,可用寫成 -

    輸出:每組一行

    • 夠用:印 OK
    • 不夠:印 SHORT 加上每一種不足的資源與缺幾個單位,格式是「字母緊接數字」,依字母順序以空白分隔,例如 SHORT C2 G1

    要求:分別數出兩個字串每個字母的個數再比較,不要用 str.replace 一個一個刪。

    範例輸入:

    2

    CCM CMMC

    GG CG

    範例輸出:

    OK

    SHORT G1

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

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

    作答登入後可作答
  3. 03

    狀態序列壓縮

    容易字串

    感測器每秒回報一個狀態字母(例如 U 是上線、D 是斷線),一天下來會產生很長的字串。存檔前用連續長度編碼(run-length)壓縮:把連續相同的字母寫成「字母+次數」,次數是 1 時只寫字母。例如 UUUUDDU 壓成 U4D2U,AAAAAAAAAAAAB 壓成 A12B。

    壓縮後沒有比較短就不划算,保留原字串。

    輸入:

    第 1 行:字串數 t

    接下來 t 行:每行一個由大寫字母組成的狀態字串(至少一個字元)

    輸出:每個字串一行

    • 壓縮後的長度小於原長度:印 RLE 壓縮後字串
    • 否則:印 RAW 原字串

    要求:用一個索引往後找出每一段連續相同字母的結尾,不要用正規表示式或 itertools.groupby。

    範例輸入:

    3

    OOOOX

    OX

    XXX

    範例輸出:

    RLE O4X

    RAW OX

    RLE X3

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

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

    作答登入後可作答