|
| 1 | +packagecom.fishercoder.solutions; |
| 2 | + |
| 3 | +importjava.util.*; |
| 4 | + |
| 5 | +/** |
| 6 | + * 465. Optimal Account Balancing |
| 7 | + * |
| 8 | + * A group of friends went on holiday and sometimes lent each other money. |
| 9 | + * For example, Alice paid for Bill's lunch for $10. |
| 10 | + * Then later Chris gave Alice $5 for a taxi ride. |
| 11 | + * We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. |
| 12 | + * Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), |
| 13 | + * the transactions can be represented as [[0, 1, 10], [2, 0, 5]]. |
| 14 | +
|
| 15 | + Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt. |
| 16 | +
|
| 17 | + Note: |
| 18 | +
|
| 19 | + A transaction will be given as a tuple (x, y, z). Note that x ? y and z > 0. |
| 20 | + 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. |
| 21 | + Example 1: |
| 22 | +
|
| 23 | + Input: |
| 24 | + [[0,1,10], [2,0,5]] |
| 25 | +
|
| 26 | + Output: |
| 27 | + 2 |
| 28 | +
|
| 29 | + Explanation: |
| 30 | + Person #0 gave person #1 $10. |
| 31 | + Person #2 gave person #0 $5. |
| 32 | +
|
| 33 | + Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each. |
| 34 | + Example 2: |
| 35 | +
|
| 36 | + Input: |
| 37 | + [[0,1,10], [1,0,1], [1,2,5], [2,0,5]] |
| 38 | +
|
| 39 | + Output: |
| 40 | + 1 |
| 41 | +
|
| 42 | + Explanation: |
| 43 | + Person #0 gave person #1 $10. |
| 44 | + Person #1 gave person #0 $1. |
| 45 | + Person #1 gave person #2 $5. |
| 46 | + Person #2 gave person #0 $5. |
| 47 | +
|
| 48 | + Therefore, person #1 only need to give person #0 $4, and all debt is settled. |
| 49 | + */ |
| 50 | +publicclass_465 { |
| 51 | +/**Reference: https://discuss.leetcode.com/topic/68948/easy-java-solution-with-explanation*/ |
| 52 | +publicintminTransfers(int[][]transactions) { |
| 53 | +if (transactions ==null ||transactions.length ==0)return0; |
| 54 | +Map<Integer,Integer>acc =newHashMap<>(); |
| 55 | +for (inti =0;i <transactions.length;i++) { |
| 56 | +intid1 =transactions[i][0]; |
| 57 | +intid2 =transactions[i][1]; |
| 58 | +intm =transactions[i][2]; |
| 59 | +acc.put(id1,acc.getOrDefault(id1,0) -m); |
| 60 | +acc.put(id2,acc.getOrDefault(id2,0) +m); |
| 61 | + } |
| 62 | +List<Integer>negs =newArrayList<>(); |
| 63 | +List<Integer>poss =newArrayList<>(); |
| 64 | +for (Integerkey :acc.keySet()) { |
| 65 | +intm =acc.get(key); |
| 66 | +if (m ==0)continue; |
| 67 | +if (m <0)negs.add(-m); |
| 68 | +elseposs.add(m); |
| 69 | + } |
| 70 | +intans =Integer.MAX_VALUE; |
| 71 | +Stack<Integer>stNeg =newStack<>(),stPos =newStack<>(); |
| 72 | +for (inti =0;i <1000;i++) { |
| 73 | +for (Integernum :negs)stNeg.push(num); |
| 74 | +for (Integernum :poss)stPos.push(num); |
| 75 | +intcur =0; |
| 76 | +while (!stNeg.isEmpty()) { |
| 77 | +intn =stNeg.pop(); |
| 78 | +intp =stPos.pop(); |
| 79 | +cur++; |
| 80 | +if (n ==p)continue; |
| 81 | +if (n >p) { |
| 82 | +stNeg.push(n -p); |
| 83 | + }else { |
| 84 | +stPos.push(p -n); |
| 85 | + } |
| 86 | + } |
| 87 | +ans =Math.min(ans,cur); |
| 88 | +Collections.shuffle(negs); |
| 89 | +Collections.shuffle(poss); |
| 90 | + } |
| 91 | +returnans; |
| 92 | + } |
| 93 | +} |