Java Recursion


  • 0
    C
    public class Solution {
        public int minTransfers(int[][] transactions) {
            //I thought it's kind of network flow problem
            Map<Integer,Integer> map = new HashMap<>();
            for(int[] t : transactions){
                map.put(t[1],map.getOrDefault(t[1],0)-t[2]);
                map.put(t[0],map.getOrDefault(t[0],0)+t[2]);
            }
            int[] count = new int[1];
            helper(map,count);
            return count[0];
        }
    //this getMax() and getMin() function is to get the index(key) of the MaxValue and MinValue
        private int getMax(Map<Integer,Integer> map){
            int max = -1;
            for(Map.Entry<Integer,Integer> entry : map.entrySet()){
                if(max == -1) max = entry.getKey();
                else if(entry.getValue() > map.get(max)){
                    max = entry.getKey();
                }
            }
            return max;
        }
        private int getMin(Map<Integer,Integer> map){
            int min = -1;
            for(Map.Entry<Integer,Integer> entry : map.entrySet()){
                if(min == -1) min = entry.getKey();
                else if(entry.getValue() < map.get(min)){
                    min = entry.getKey();
                }
            }
            return min;
        }
    
        private void helper(Map<Integer,Integer> map, int[] count){
            int max = getMax(map);
            int min = getMin(map);
    //This means richest one and poorest one are both $0, means balance.
            if(map.get(max) == 0 && map.get(min) == 0) return;
            //Or we get the min abs value of max and min
            int minValue = Math.min(map.get(max),-map.get(min));
           //let the richest give the poorest the as much as possible money
            map.put(max, map.get(max)-minValue);
            map.put(min, map.get(min)+minValue);
          //after done this, add the count
            count[0]++;
            helper(map,count);
        }
    }

  • 0
    D

    Wont work for this test case:
    [[2,0,5],[4,3,4]]. The code output will be 3 but expected output is 2.


  • 0
    C

    @doubleD
    My code output is 2....


  • 0
    Y

    @chnsht
    If we have the case that persons of (2, 50, 50, ..., 50) need to pay the persons of (51, 50, 50, ..., 50, 51), obviously we could get the minimal number of transactions by letting person "2" pay $1 to both the first and last person of (51, 50, 50, ..., 50, 51) and each person "50" pays one person $50.

    However, seems your solution doesn't go through this "payment plan". (This example may not be a good one, but you know what I mean.)


  • 0
    Y

    @chnsht said in Java Recursion:
    For the test case:
    {{1, 8, 1}, {1, 13, 21}, {2, 8, 10}, {3, 9, 20}, {4, 10, 61}, {5, 11, 61}, {6, 12, 59}, {7, 13, 60}}

    Your solution returns 9, however, the correct answer should be 8. There are 8 transactions here and the answer should not be larger than 8.


  • 0
    C

    @yuhaowang001
    Ok, I will check my solution again, thanks for pointing out!


Log in to reply
 

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