|
7 | 7 | import java.util.Map;
|
8 | 8 | import java.util.Stack;
|
9 | 9 |
|
10 |
| -/** |
11 |
| - * 465. Optimal Account Balancing |
12 |
| - * |
13 |
| - * A group of friends went on holiday and sometimes lent each other money. |
14 |
| - * For example, Alice paid for Bill's lunch for $10. |
15 |
| - * Then later Chris gave Alice $5 for a taxi ride. |
16 |
| - * We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. |
17 |
| - * Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), |
18 |
| - * the transactions can be represented as [[0, 1, 10], [2, 0, 5]]. |
19 |
| -
|
20 |
| - Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt. |
21 |
| -
|
22 |
| - Note: |
23 |
| -
|
24 |
| - A transaction will be given as a tuple (x, y, z). Note that x ? y and z > 0. |
25 |
| - 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. |
26 |
| - Example 1: |
27 |
| -
|
28 |
| - Input: |
29 |
| - [[0,1,10], [2,0,5]] |
30 |
| -
|
31 |
| - Output: |
32 |
| - 2 |
33 |
| -
|
34 |
| - Explanation: |
35 |
| - Person #0 gave person #1 $10. |
36 |
| - Person #2 gave person #0 $5. |
37 |
| -
|
38 |
| - Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each. |
39 |
| - Example 2: |
40 |
| -
|
41 |
| - Input: |
42 |
| - [[0,1,10], [1,0,1], [1,2,5], [2,0,5]] |
43 |
| -
|
44 |
| - Output: |
45 |
| - 1 |
46 |
| -
|
47 |
| - Explanation: |
48 |
| - Person #0 gave person #1 $10. |
49 |
| - Person #1 gave person #0 $1. |
50 |
| - Person #1 gave person #2 $5. |
51 |
| - Person #2 gave person #0 $5. |
52 |
| -
|
53 |
| - Therefore, person #1 only need to give person #0 $4, and all debt is settled. |
54 |
| - */ |
55 | 10 | public class _465 {
|
56 | 11 | public static class Solution1 {
|
57 | 12 | /**
|
|
0 commit comments