算法

(DFS)

时间复杂度分析：DFS 的时间复杂度是多少哇

C++ 代码

class Solution {
public:
    int minTransfers(vector<vector<int>>& transactions) {
        // 原来一个二维矩阵就可以了啊，我还用hashmap 搞得这么复杂
        // DFS 
        // 这个题目一上来不知道怎么做啊
        // 先把transaction 变成 account balance
        // 然后dfs 每次drop 掉一个 account
        // 每次drop 掉一个account， 这是说最多drop n-1 么， n 是一开始的账户数目
        // why the answer ranked top 1 sets the res to INT_MAX?
        // don't know why
        // what is prev
        // 我感觉我好像有点看懂这个题目了
        // 每一次都找一个与当前account balance whose sign is different from the current account
        // and then drop out the current account by add the current account's balance to the one that found to have 
        // different sign balance from the current account
        // in this way, we can erase one account balance each time, in other words, make at least one account's balance equal to 0
        // by doing this step by step, we can make all the accounts' balance equal to 0, if all the accounts' balance equal to 0
        // which means the debts have been settled.
        // during that process, each time, when we erase one account, we add 1 to the current count of the transactions that have been processed
        // after all the debts have been settled, we have a transaction counter value, but that's just one way to settle all the transactions, we need to try out all the possible ways to settle the transaction, and keep track of the minimum value of the transaction counter needed to settle all the debts.
        // which means we need to try out all possible ways, and each time when we finish all the transactions, in other words, make all accounts' balance equal to 0, we then need to backtrack, to try other choices.
        // 好了， 我要开始写code 了
        // start 是为了去重用的
        // 首先 traverse 所有transactions, 把transactions 转化成 account balance
        // transactions: n X 3 matrix
        int max_transac = transactions.size();
        unordered_map<int, int> ac2bal;
        for (int i = 0; i < transactions.size(); i++) {
            vector<int> cur_transaction = transactions[i];
            ac2bal[cur_transaction[0]] -= cur_transaction[2];
            ac2bal[cur_transaction[1]] += cur_transaction[2];
        }
        // 因为unordered_map 不太好traverse, 所以把这个map  转化成 vector
        // 题目当中还特意提醒说index 没有关系，所以 index  是什么不重要，只要这是一个unique 的index, 可以代表这个账户就好，因此vector 的index 
        // 就可以代表这个账户了，或者说代表这个人了，所以其实这个人一开始的编号并不需要存下来
        vector<int> account_balance;
        for (auto pair : ac2bal) {
            if (pair.second) {
                account_balance.push_back(pair.second);
            }
        }
        // 然后我们就需要调用dfs helper function 去把这一堆不为0 的账户一个一个清掉了
          return dfs(account_balance, 0);        
    }
private:
    //  这里来写我们的helper function
    int dfs(vector<int>& account_balance, int start) {
        int n = account_balance.size();
        // start 就是我们当前要消除的账户， 这个账户的balance 不能为0，因为如果已经为0了还消除个啥，不用消除，直接跳过
        while (start < n && account_balance[start] == 0) {
            start++;
        }
        // 我们总是从第一个账户开始消除
        // 然后我们从第一个账户的下一个账户开始找起
        if (start == n) return 0;
        int res = INT_MAX;

        for (int i = start+1; i < n; i++) {
            // 如果他们刚好账户balance 正负相反，就可以消除了
            //  之所以不找正正的balance来消除，是因为明显这样消除，transaction 会越变越多的
            if ( account_balance[i] * account_balance[start] < 0) {
                // 满足条件了，我们来消除吧 ( 相加才是消除朋友们，debug了好久发现了这个问题)
                account_balance[i] += account_balance[start];
                // start 前面包括start 都是已经消除过的
                res = min(res, 1 + dfs(account_balance, start+1));
                account_balance[i] -= account_balance[start];
            }
        }
        return res;
    }
};