Leetcode 465. Optimal Account Balancing (python+cpp)

题目

解析：

这个题目手下需要进行一些预处理，这一系列的转账可以被全部简化成每个账户进行这些转账之后最后需要支出或者收入多少钱。

这个问题有许多的解法，但是我个人认为比较make sense的一种就是利用backtracking枚举所有可能的方式。具体如下：

• 从第一个账户开始，我们现在的目标是，清空第一个账户，那么就意味着可以将第一个账户的余额加到后面任意一个非0切正负与第一个账户余额相反的账户上
• 然后进行下一层dfs，下一层dfs就以非0的账户为起点开始
• 需要注意的是，由于我们并不清楚有没有后面的账户在第一个账户被清0的时候也同时清0，所以需要设计一个while训话来跳过这些0
• 同时由于是枚举所有不同的方法，所以是需要backtracking操作的

python代码：

class Solution:def minTransfers(self, transactions: List[List[int]]) -> int:def helper(account,start,count):nonlocal answhile start<len(account) and account[start]==0:start += 1if start==len(account):ans = min(count,ans)return for i in range(start+1,len(account)):if account[i]*account[start] < 0:account[i] += account[start]helper(account,start+1,count+1)account[i] -= account[start]memo = collections.defaultdict(int)for t in transactions:memo[t[0]] -= t[2]memo[t[1]] += t[2]account = []for k,v in memo.items():if v!=0:account.append(v)ans = float('inf')helper(account,0,0)return ans

C++如下：

class Solution {
    int ans=INT_MAX;
public:int minTransfers(vector<vector<int>>& transactions) {
    unordered_map<int,int> memo;for (auto t:transactions){
    memo[t[0]] -= t[2];memo[t[1]] += t[2];}vector<int> account;for (auto m:memo){
    if (m.second!=0) account.push_back(m.second);}helper(account,0,0);return ans;}void helper(vector<int>& account,int start,int count){
    int n=account.size();while (start<n && account[start]==0) ++start;if (start==n){
    ans = min(ans,count);}for (int i=start+1;i<n;i++){
    if (account[start]*account[i]<0){
    account[i] += account[start];helper(account,start+1,count+1);account[i] -= account[start];}}}
};

其实这道题目说到底这道题目也就是个brutal force而已，我没有想到更加优化且直观的方法

二刷

这道题目其实挺难的。本质上在于对于一堆数有正有负，把他们assign到若干个sub-group，要求每个sub-group总和为0.总体的思路就会相识产生combination。
dfs的核心思想在于，每层都保证清空一个账户，不管清空这个账户时其他的账户会发生什么样的变化。这样才能保证到最后每个账户清零
可以优化的一点在于，可以讲账户进行排序，这样就可以跳过相同的组合。比如现在需要清空账户a，如果账户b和账户c的值相同，那么用b和c来平衡账户a本质效果都是一样的

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>using namespace std;
void helper(vector<int>& debt,int start,int& ans, int trans){
    // cout << start << endl;while(start < debt.size() && debt[start] == 0) start++;if(start == debt.size()) {
    ans = min(ans,trans);return;}for(int i=start+1;i<debt.size();i++){
    if(i > start+1 && debt[i] == debt[i-1]) continue;if(debt[start] * debt[i] < 0){
    debt[i] += debt[start];helper(debt,start+1,ans,trans+1);debt[i] -= debt[start];}}
}int minTransfer(vector<vector<int>>& transactions){
    unordered_map<int,int> memo;for(auto& it : transactions){
    memo[it[0]] -= it[2];memo[it[1]] += it[2];}vector<int> debt;for(auto it : memo){
    if(it.second != 0) debt.push_back(it.second);}sort(debt.begin(),debt.end());int ans = 100000;helper(debt,0,ans,0);return ans;}int main()
{
    vector<vector<int>> transactions{
    {
    0,1,10},{
    2,0,5}};// vector<vector<int>> transactions{
    {0,1,10},{1,0,1},{1,2,5},{2,0,5}};int ans = minTransfer(transactions);cout << ans << endl;return 0;
}