[LeetCode] 465. Optimal Account Balancing 最优帐户平衡

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 465. 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.ThenlaterChrisgaveAlice10.ThenlaterChrisgaveAlice5 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]].html

Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.java

Note:python

  1. A transaction will be given as a tuple (x, y, z). Note that x ≠ y and z > 0.
  2. 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:app

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.

一堆人出去度假,你们互相帮别人垫付过钱,最后结算平衡总花费,可能你欠着别人的钱,其余人可能也欠你的钱,有的帐就不用还了,找出最少须要多少次交易。ide

解法: 首先计算出每一个人的最后盈亏,而后用随机的算法找到比较可能的最小值。对于全部交易,每一个人最终将有一个总负债bal[id],全部负债为0的人不须要支付交易,用一个精炼的负债表debt[]表示负债不为零的用户的负债信息,其中:debt[i] > 0 表示该人须要向其余人支付debt[i]的金钱;debt[i] < 0 表示该人须要接受来自其余人总计debt[i]的金钱。
从第一个负债debt[0]开始,看看全部它后面的人的负债信息,当搜索到第一个和debt负债信息sign相反的人i的信息时,就试图平衡这两我的之间的负债关系(即在0和i之间产生一个交易,使得debt[0]为0)。今后之后,用户0就负债清零了,因此再递归地查找后面的负债清零情况。在DFS的过程当中,能够维护一个最小的交易次数,并最终返回。post

谷歌题ui

Java:url

public class Solution {
    public int minTransfers(int[][] transactions) {
        Map<Integer, Integer> balances = new HashMap<>();
        for(int[] tran: transactions) {
            balances.put(tran[0], balances.getOrDefault(tran[0], 0) - tran[2]);
            balances.put(tran[1], balances.getOrDefault(tran[1], 0) + tran[2]);
        }
        List<Integer> poss = new ArrayList<>();
        List<Integer> negs = new ArrayList<>();
        for(Map.Entry<Integer, Integer> balance : balances.entrySet()) {
            int val = balance.getValue();
            if (val > 0) poss.add(val);
            else if (val < 0) negs.add(-val);
        }
        int min = Integer.MAX_VALUE;
        Stack<Integer> ps = new Stack<>();
        Stack<Integer> ns = new Stack<>();
        for(int i = 0; i < 10; i++) {
            for(int pos: poss) {
                ps.push(pos);
            }
            for(int neg: negs) {
                ns.push(neg);
            }
            int count = 0;
            while (!ps.isEmpty()) {
                int p = ps.pop();
                int n = ns.pop();
                if (p > n) {
                    ps.push(p - n);
                } else if (p < n) {
                    ns.push(n - p);
                }
                count++;
            }
            min = Math.min(min, count);
            Collections.shuffle(poss);
            Collections.shuffle(negs);
        }
        return min;
    }
}  

Java:spa

public int minTransfers(int[][] transactions) {
    if (transactions == null || transactions.length == 0 || transactions[0].length == 0)
        return 0;
    //calculate delta for each account
    Map<Integer, Integer> accountToDelta = new HashMap<Integer, Integer>();
    for (int[] transaction : transactions) {
        int from = transaction[0];
        int to = transaction[1];
        int val = transaction[2];
        if (!accountToDelta.containsKey(from)) {
            accountToDelta.put(from, 0);
        }
        if (!accountToDelta.containsKey(to)) {
            accountToDelta.put(to, 0);
        }
        accountToDelta.put(from, accountToDelta.get(from) - val);
        accountToDelta.put(to, accountToDelta.get(to) + val);
    }
    List<Integer> deltas = new ArrayList<Integer>();
    for (int delta : accountToDelta.values()) {
        if (delta != 0)
            deltas.add(delta);
    }
    //since minTransStartsFrom is slow, we can remove matched deltas to optimize it
    //for example, if account A has balance 5 and account B has balance -5, we know
    //that one transaction from B to A is optimal.
    int matchCount = removeMatchDeltas(deltas);
    //try out all possibilities to get minimum number of transactions
    return matchCount + minTransStartsFrom(deltas, 0);
}
 
private int removeMatchDeltas(List<Integer> deltas) {
    Collections.sort(deltas);
    int left = 0;
    int right = deltas.size() - 1;
    int matchCount = 0;
    while (left < right) {
        if (-1 * deltas.get(left) == deltas.get(right)) {
            deltas.remove(left);
            deltas.remove(right - 1);
            right -= 2;
            matchCount++;
        } else if (-1 * deltas.get(left) > deltas.get(right)) {
            left++;
        } else {
            right--;
        }
    }
    return matchCount;
}
 
private int minTransStartsFrom(List<Integer> deltas, int start) {
    int result = Integer.MAX_VALUE;
    int n = deltas.size();
    while (start < n && deltas.get(start) == 0)
        start++;
    if (start == n)
        return 0;
    for (int i = start + 1; i < n; i++) {
        if ((long) deltas.get(i) * deltas.get(start) < 0) {
            deltas.set(i, deltas.get(i) + deltas.get(start));
            result = Math.min(result, 1 + minTransStartsFrom(deltas, start + 1));
            deltas.set(i, deltas.get(i) - deltas.get(start));
    }
    }
    return result;
}  

Python:

# Time:  O(n * 2^n), n is the size of the debt.
# Space: O(n * 2^n)
import collections

class Solution(object):
    def minTransfers(self, transactions):
        """
        :type transactions: List[List[int]]
        :rtype: int
        """
        account = collections.defaultdict(int)
        for transaction in transactions:
            account[transaction[0]] += transaction[2]
            account[transaction[1]] -= transaction[2]

        debt = []
        for v in account.values():
            if v:
                debt.append(v)

        if not debt:
            return 0

        n = 1 << len(debt)
        dp, subset = [float("inf")] * n, []
        for i in xrange(1, n):
            net_debt, number = 0, 0
            for j in xrange(len(debt)):
                if i & 1 << j:
                    net_debt += debt[j]
                    number += 1
            if net_debt == 0:
                dp[i] = number - 1
                for s in subset:
                    if (i & s) == s:
                        dp[i] = min(dp[i], dp[s] + dp[i - s])
                subset.append(i)
        return dp[-1]  

C++:

class Solution {
public:
    int minTransfers(vector<vector<int>>& transactions) {
        unordered_map<int, int> m;
        for (auto t : transactions) {
            m[t[0]] -= t[2];
            m[t[1]] += t[2];
        }
        vector<int> accnt(m.size());
        int cnt = 0;
        for (auto a : m) {
            if (a.second != 0) accnt[cnt++] = a.second;
        }
        return helper(accnt, 0, cnt, 0);
    }
    int helper(vector<int>& accnt, int start, int n, int num) {
        int res = INT_MAX;
        while (start < n && accnt[start] == 0) ++start;
        for (int i = start + 1; i < n; ++i) {
            if ((accnt[i] < 0 && accnt[start] > 0) || (accnt[i] > 0 && accnt[start] < 0)) {
                accnt[i] += accnt[start];
                res = min(res, helper(accnt, start + 1, n, num + 1));
                accnt[i] -= accnt[start];
            }
        }
        return res == INT_MAX ? num : res;
    }
};  

C++:

class Solution {
public:
    int minTransfers(vector<vector<int>>& transactions) {
        unordered_map<int, long> bal;   // each person's overall balance
        for(auto &t: transactions) {
            bal[t[0]] -= t[2];
            bal[t[1]] += t[2];
        }
        for(auto &p: bal) {
            if(p.second) {
                debt.push_back(p.second);
            }
        }
        return dfs(0, 0);
    }
private:
    int dfs(int s, int cnt) {                       // min number of transactions to settle starting from debt[s]
    	while (s < debt.size() && !debt[s]) {
            ++s;                                    // get next non-zero debt
        }
    	int res = INT_MAX;
    	for (long i = s + 1, prev = 0; i < debt.size(); ++i) {
            if (debt[i] != prev && debt[i] * debt[s] < 0) {     // skip already tested or same sign debt
                debt[i] += debt[s];
                res = min(res, dfs(s + 1,cnt + 1));             // backtracking
                debt[i] -= debt[s];
                prev = debt[i];
            }
        }
    	return res < INT_MAX? res : cnt;
    }
    vector<long> debt;                              // all non-zero balances
};

C++:

class Solution {
public:
    int minTransfers(vector<vector<int>>& transactions) {
        unordered_map<int, int> mp;
        for (auto x : transactions) {
            mp[x[0]] -= x[2];
            mp[x[1]] += x[2];
        }
        vector<int> in;
        vector<int> out;
        for (auto x : mp) {
            if (x.second < 0) out.push_back(-x.second);
            else if (x.second > 0) in.push_back(x.second);
        }
        int amount = 0;
        for (auto x : in) amount += x;
        if (amount == 0) return 0;
        int res = (int)in.size() + (int)out.size() - 1;
        dfs(in, out, 0, 0, amount, 0, res);
        return res;
    }
    
    void dfs(vector<int> &in, vector<int> &out, int i, int k, 
             int amount, int step, int &res) {
        if (step >= res) return;
        if (amount == 0) {
            res = step;
            return;
        }
        if (in[i] == 0) {
            ++i;
            k = 0;
        }
        for (int j = k; j < out.size(); j++) {
            int dec = min(in[i], out[j]);
            if (dec == 0) continue;
            in[i] -= dec;
            out[j] -= dec;
            dfs(in, out, i, j + 1, amount - dec, step + 1, res);
            in[i] += dec;
            out[j] += dec;
        }
    }
};

  

  

 

All LeetCode Questions List 题目汇总