演算法初階・字串的基本操作
逐字元比對找共同前綴、字母計數比較配額、連續長度編碼壓縮狀態字串。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 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 執行,只用標準函式庫。
作答登入後可作答 - 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 執行,只用標準函式庫。
作答登入後可作答 - 夠用:印
- 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 執行,只用標準函式庫。
作答登入後可作答 - 壓縮後的長度小於原長度:印

送件鴿飛出去了