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

演算法初階・雙指標與排序後處理

利用資料已排序:原地去重、左右指標湊預算、兩份清單找交集。

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

  1. 01

    已排序事件編號去重

    容易雙指標

    訊息佇列「至少送達一次」,消費端收到的事件編號已由小到大排序,但同一個事件可能被送了好幾次。請原地去重:把不重複的編號依序搬到 list 的前段。

    輸入:一行,由小到大排序的事件編號(整數,以空白分隔,至少一筆)

    輸出:兩行

    第 1 行:不重複的事件數 k

    第 2 行:去重後的編號(list 前 k 個),以空白分隔

    要求:用「寫入位置」與「讀取位置」兩個指標在同一個 list 上完成,不要用 set,也不要另外建新的 list。

    範例輸入:

    7 7 8 9 9

    範例輸出:

    3

    7 8 9

    類型對應:LeetCode「Remove Duplicates from Sorted Array」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答
  2. 02

    已排序報價湊預算

    容易雙指標

    採購要從報價清單挑兩個不同的品項,價格加起來剛好等於預算。報價已由小到大排序,而且每個價格都不同。

    輸入:

    第 1 行:預算 budget

    第 2 行:由小到大排序的價格(整數,以空白分隔,彼此不同)

    輸出:一行 較低價 較高價;有多組時,取「較低價」最小的那一組;找不到印 NONE。

    要求:用左右兩個指標往中間走(一次走完),不要兩層迴圈試所有組合。

    範例輸入:

    90

    15 30 45 60 75

    範例輸出:

    15 75

    類型對應:LeetCode「Two Sum II - Input Array Is Sorted」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答
  3. 03

    兩系統共同主鍵

    容易雙指標

    對帳時要找出「兩個系統都有」的客戶編號。兩個系統各匯出一份已由小到大排序的客戶編號,每份清單內沒有重複。

    輸入:

    第 1 行:系統 A 的客戶編號(整數,已排序,以空白分隔;沒有資料時是空行)

    第 2 行:系統 B 的客戶編號(格式同上)

    輸出:一行,兩邊都有的客戶編號由小到大、以空白分隔;沒有共同的印 NONE。

    要求:利用兩份都已排序,用兩個指標一次走完,不要用 set,也不要對 A 的每一筆去 B 裡面搜尋。

    範例輸入:

    3 8 12 20

    1 8 20 25

    範例輸出:

    8 20

    類型對應:LeetCode「Intersection of Two Arrays」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答