Problem:
Optimal Account Balancing: A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill's lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transactions can be represented as [[0, 1, 10], [2, 0, 5]].
Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.
Note:
A transaction will be given as a tuple (x, y, z). Note that x รข‰ y and z > 0.
Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.
Optimal Account Balancing: A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill's lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transactions can be represented as [[0, 1, 10], [2, 0, 5]].
Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.
Note:
A transaction will be given as a tuple (x, y, z). Note that x รข‰ y and z > 0.
Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.
Example 1:
- Input: [[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: [[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.
We can use a hash table to establish a mapping between each person and their account. If the account is positive, it means that the other person owes you money; if the account is negative, you owe someone else money. For each bill, the previous person subtracts the amount of money from the hash table, and the latter adds the amount of money to the hash table. So each of us has an account, and then what we need to do next is to consolidate the account and see how many remittances are needed at least.
We first count the number of people whose account value is not 0, because if it is 0, it means that you don't owe money to others, and others don't owe you money. If it is not 0, we put the money into an array of accnt, then Call the recursive function. In the recursive function, we initialize the result res to the integer maximum, then we skip the account with 0, then we start to traverse the subsequent account, if the current account and the previous account have positive and negative money, we will be the previous one The amount of money in the account is added to the current account.
Then we call the recursive function, then start from the currently changed account, num represents the current transfer number, need to add 1, then we use the result returned by this recursive function to update res, do not forget to restore the value of the current account . After the traversal, we see that the value of res is still the maximum value of the integer, indicating that it has not changed, we return num, otherwise we can return res.
Solution:
We first count the number of people whose account value is not 0, because if it is 0, it means that you don't owe money to others, and others don't owe you money. If it is not 0, we put the money into an array of accnt, then Call the recursive function. In the recursive function, we initialize the result res to the integer maximum, then we skip the account with 0, then we start to traverse the subsequent account, if the current account and the previous account have positive and negative money, we will be the previous one The amount of money in the account is added to the current account.
Then we call the recursive function, then start from the currently changed account, num represents the current transfer number, need to add 1, then we use the result returned by this recursive function to update res, do not forget to restore the value of the current account . After the traversal, we see that the value of res is still the maximum value of the integer, indicating that it has not changed, we return num, otherwise we can return res.
Solution:
time complexity?
ReplyDelete