本文主要是介绍leetcode - 465. Optimal Account Balancing,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Description
You are given an array of transactions transactions where transactions[i] = [fromi, toi, amounti] indicates that the person with ID = fromi gave amounti $ to the person with ID = toi.
Return the minimum number of transactions required to settle the debt.
Example 1:
Input: transactions = [[0,1,10],[2,0,5]]
Output: 2
Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.
Example 2:
Input: transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
Output: 1
Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.
Therefore, person #1 only need to give person #0 $4, and all debt is settled.
Constraints:
1 <= transactions.length <= 8
transactions[i].length == 3
0 <= fromi, toi < 12
fromi != toi
1 <= amounti <= 100
Solution
Solved after help.
Run a debt list, to store all the balance of people. Then backtrace, try every transaction.
Time complexity: o ( 2 n ) = o ( 2 8 ) o(2^n)=o(2^8) o(2n)=o(28)
Space complexity: o ( n ) o(n) o(n)
Code
class Solution:def minTransfers(self, transactions: List[List[int]]) -> int:people = {}for p1, p2, amount in transactions:people[p1] = people.get(p1, 0) - amountpeople[p2] = people.get(p2, 0) + amountdebts = [value for value in people.values() if value != 0]def dfs(start_index: int) -> int:if start_index == len(debts):return 0if debts[start_index] == 0:return dfs(start_index + 1)res = float('inf')for i in range(start_index + 1, len(debts)):if debts[i] * debts[start_index] < 0:debts[i] += debts[start_index]res = min(res, 1 + dfs(start_index + 1))debts[i] -= debts[start_index]return res if res != float('inf') else 0return dfs(0)
这篇关于leetcode - 465. Optimal Account Balancing的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!