官方解答｜雙路狀態對照

官方解答

Python #473：雙路狀態對照

解題規則

模擬器把每筆訊號送往兩個獨立狀態盒之一，請保存分流與狀態紀錄。

用同一個Bucket類別建立兩個獨立物件：左value初始為initial，右value初始為0；各自count為0、received為空清單。依原順序處理changes，每筆只送一邊。分流規則：「amount大於或等於0時送左，否則送右」。所有判斷使用該筆處理前的狀態。接收物件將value改成「目前value加amount」，再將count加1、把原amount加入received；另一邊完全不變。每一步都保存 [左value,右value] 快照，最後回傳[左value,右value,左收件數,右收件數]。

處理步驟

建立兩個獨立 Bucket；依目前的左右狀態決定收件者，只有收件物件更新數值與收件數，然後保存雙值快照。

為何正確

物件屬性保存當前狀態；負責更新的方法依當時屬性完成一次更新與必要的快照，讀值步驟只讀取目前屬性。初始化及逐次更新維持題目指定的狀態，因此最後回傳的資料符合指定摘要。

邊界與注意事項

本題輸入範圍：initial 為 -10～10；changes 長度0～8，每個數為 -6～6。索引從0開始，每一步必須使用當時狀態。 除題目指定的篩選或移除外，保留原資料的重複項與順序；使用切片或明確判斷安全處理允許的空資料。 需要清單快照時另外複製，兩個物件的清單與計數彼此獨立。

範例追蹤

依參數順序 initial, changes 傳入 [4,[0,-2,0,3]]。關鍵中間資料為 left = {'value': 7, 'count': 3, 'received': [0, 0, 3]}；right = {'value': -2, 'count': 1, 'received': [-2]}；history = [[4, 0], [4, -2], [4, -2], [7, -2]]；index = 3。最後回傳 [7, -2, 3, 1]。結果由 return 回傳，不使用 print。

複雜度

設輸入及必要輸出的總大小為 n；複製、轉換或掃描最壞時間 O(n)，保存中間資料與回傳結果最壞需要 O(n) 空間。

class Bucket:

    def __init__(self, initial):
        self.value = initial
        self.count = 0
        self.received = []

    def accept(self, amount):
        self.value = self.value + amount
        self.count += 1
        self.received.append(amount)

def solve(initial, changes):
    left = Bucket(initial)
    right = Bucket(0)
    history = []
    for (index, amount) in enumerate(changes):
        if amount >= 0:
            left.accept(amount)
        else:
            right.accept(amount)
        history.append([left.value, right.value])
    return [left.value, right.value, left.count, right.count]