straightforward short AC BFS python code, but hope someone can help me reduce running time


  • 0
    Y
        def minTransfers(self, transactions):
            """
            :type transactions: List[List[int]]
            :rtype: int
            """
            money = {}
            for transaction in transactions:
                if transaction[0] in money:
                   money[transaction[0]] -= transaction[2]
                else:
                   money[transaction[0]] = -transaction[2]
                if transaction[1] in money:
                   money[transaction[1]] += transaction[2]
                else:
                   money[transaction[1]] = transaction[2]
            queue = [[0, money.values()]]
            while queue:
                head = queue.pop(0)
                ans, top = head[0], head[1]
                k, n = len(top), len(top)
                for i in range(n):
                    if top[i]:
                       k = i
                       break
                for j in range(k+1, n):
                    if top[j] and top[k] ^ top[j] < 0:
                       amount_k, amount_j = top[k], top[j]
                       if abs(top[k]) <= abs(top[j]):
                          top[k], top[j] = 0, top[j] + amount_k
                       else:
                          top[k], top[j] = top[k] + amount_j, 0
                       if all(v == 0 for v in top):
                          return ans + 1
                       queue.append([ans + 1, list(top)])
                       top[k], top[j] = amount_k, amount_j
            return 0

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.