官方解答｜雙站逐步讀取

官方解答

Python #221：雙站逐步讀取

解題規則

兩個讀取頭各自查看一站的資料，每一步只推進其中一個讀取頭。

左游標 i、右游標 j 都從0開始。只要左右都還有資料，用 while 比較兩個游標所在的原值。符合「兩值相等」時只把左游標加1，否則只把右游標加1。每次推進前記錄 [左索引,右索引,將推進的「左」或「右」,左值減右值]。任一邊走完就停止。回傳 [紀錄清單,左邊未處理部分,右邊未處理部分]。

處理步驟

比較目前左右原值，先留下推進前的索引、方向與轉換結果，再且只再推進指定的一邊。

為何正確

每次迴圈開始時，游標指向下一個尚未處理的位置，state 表示已處理資料的狀態。停止條件放在題目要求的更新前或更新後，游標與歷史就能正確區分已讀和未讀資料。

邊界與注意事項

本題輸入範圍：每份長度 0～12；每個值為 -100～100 的整數。 除題目指定的篩選或移除外，保留原資料的重複項與順序；使用切片或明確判斷安全處理允許的空資料。

範例追蹤

依參數順序 left, right 傳入 [[3,-2,0],[3,0,-2]]。關鍵中間資料為 i = 2；j = 3；history = [[0, 0, '左', 0], [1, 0, '右', -5], [1, 1, '右', -2], [1, 2, '左', 0], [2, 2, '右', 2]]；move_left = False。最後回傳 [[[0, 0, '左', 0], [1, 0, '右', -5], [1, 1, '右', -2], [1, 2, '左', 0], [2, 2, '右', 2]], [0], []]。結果由 return 回傳，不使用 print。

複雜度

設輸入總長度 n；游標或迴圈逐次前進，最壞時間 O(n)，保存歷史與回傳結果最壞需要 O(n) 空間。

def solve(left, right):
    i = j = 0
    history = []
    while i < len(left) and j < len(right):
        move_left = left[i] == right[j]
        history.append([i, j, '左' if move_left else '右', left[i] - right[j]])
        if move_left:
            i += 1
        else:
            j += 1
    return [history, left[i:], right[j:]]