3ms of C++, easy to understand


  • 1
    T

    The idea is to use two different vectors to store borrowers and lenders. By this, we needn't worry about ignoring zero value.

    	int dfs(vector<int>& lders, vector<int>&bwers, int m, int n)
    	{
    		if (m == lders.size()) return 0;
    		if (m == lders.size() - 1) return bwers.size() - n;
    		if (n == bwers.size() - 1) return lders.size() - m;
    		int minVal = INT_MAX;
    		for (int i = m; i < lders.size(); i++)
    		{
    		        if (lders[i] == bwers[n])
    				return 1 + dfs(lders, bwers, m+1, n + 1);
    		    
    			if (lders[i] > bwers[n])
    			{
    				lders[i] -= bwers[n];
    				minVal = min(minVal, 1 + dfs(lders, bwers, m, n + 1));
    				lders[i] += bwers[n];
    			}
    			else
    			{
    				bwers[n] -= lders[i];
    				minVal = min(minVal, 1 + dfs(lders, bwers, m + 1, n));
    				bwers[n] += lders[i];
    			}
    		}
    		return minVal;
    	}
    
    	int minTransfers(vector<vector<int>>& transactions) {
    		unordered_map<int, int> gaps;
    		for (auto& tr : transactions)
    		{
    			gaps[tr[0]] -= tr[2]; 
    			gaps[tr[1]] += tr[2];
    		}
    		
    		vector<int> lenders, borrowers;
    		for (auto& pr : gaps)
    			if (pr.second < 0)
    				lenders.push_back(-pr.second);
    			else if (pr.second > 0)
    				borrowers.push_back(pr.second);
    		return dfs(lenders, borrowers, 0, 0);
    	}

  • 0
    H
    if (lders[i] == bwers[n])
        return 1 + dfs(lders, bwers, m+1, n + 1);
    

    if i > m, it will skip the debt of lders[m], for example:
    lders = [ 3, 15, 6, 7], m = 0, i = 2
    bwers = [6, 12, 9, 4], n = 0

    The problem doesn't provide a way to make the inputs well controlled. If it allows to directly input the 2 arrays, it will be easier to verify if the algorithm correct or not.


Log in to reply
 

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