📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3311| 回复: 5
跳转到指定楼层
上一主题 下一主题
收起左侧

詢問 LC 465. Optimal Account Balancing

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
leetcode.com/problems/optimal-account-balancing/discuss/95355/11-liner-9ms-DFS-solution-(detailed-explanation)/142043

這道題看了許久,還是不能理解 dfs 部分是如何進行的。
為何 dfs 是在 for 迴圈裡面做呢?不是要先從 start balance 後面的所有值,再從 start + 1 開始 balance 嗎?請問這解法應該要如何理解呢?謝謝。

public int minTransfers(int[][] transactions) {        Map<Integer, Integer> m = new HashMap<>();        for (int[] t : transactions) {            m.put(t[0], m.getOrDefault(t[0], 0) - t[2]);            m.put(t[1], m.getOrDefault(t[1], 0) + t[2]);        }        return settle(0, new ArrayList<>(m.values()));    }    int settle(int start, List<Integer> debt) {        while (start < debt.size() && debt.get(start) == 0)            start++;        if (start == debt.size()) return 0;        int r = Integer.MAX_VALUE;        for (int i = start + 1; i < debt.size(); i++)            if (debt.get(start) * debt.get(i) < 0) {                debt.set(i, debt.get(i) + debt.get(start));                r = Math.min(r, 1 + settle(start + 1, debt));                debt.set(i, debt.get(i) - debt.get(start));            }        return r;    }

评分

参与人数 1大米 +3 收起 理由
yingciou + 3 謝謝分享好問題

查看全部评分


上一篇:用Ruby写算法题合适么
下一篇:终于来开贴刷题了
推荐
stellari 2018-10-3 10:23:06 | 只看该作者
全局:
要消除第start号人的负债,可能的策略是将其债务全部转给stat+1号,start+2号,……,N号中之一(也就是debt.set(i, debt.get(i) + debt.get(start));这一句),最多N-start种策略。(不需考虑将start债务转给0, ... , start -1的情况,因为这些情况在之前消除0,1,……,start-1号这些人的负债时已经考虑过了)

每次调用settle函数时,必须尝试所有这些策略,然后在每种策略的基础上再考虑如何消除start+1号的负债。因此需要一个循环来遍历这些策略,并在循环中进一步调用settle(start+1)



评分

参与人数 1大米 +3 收起 理由
linnumberone + 3 謝謝加入討論!

查看全部评分

回复

使用道具 举报

全局:
这题我自己想了很久.. 没想明白..

看明白了我回你
回复

使用道具 举报

🔗
 楼主| linnumberone 2018-10-2 08:10:49 | 只看该作者
全局:
沒注意到程式的格式,請參考:

  1. public int minTransfers(int[][] transactions) {
  2.         Map<Integer, Integer> m = new HashMap<>();
  3.         for (int[] t : transactions) {
  4.             m.put(t[0], m.getOrDefault(t[0], 0) - t[2]);
  5.             m.put(t[1], m.getOrDefault(t[1], 0) + t[2]);
  6.         }
  7.         return settle(0, new ArrayList<>(m.values()));
  8.     }

  9.     int settle(int start, List<Integer> debt) {
  10.         while (start < debt.size() && debt.get(start) == 0)
  11.             start++;
  12.         if (start == debt.size()) return 0;
  13.         int r = Integer.MAX_VALUE;
  14.         for (int i = start + 1; i < debt.size(); i++)
  15.             if (debt.get(start) * debt.get(i) < 0) {
  16.                 debt.set(i, debt.get(i) + debt.get(start));
  17.                 r = Math.min(r, 1 + settle(start + 1, debt));
  18.                 debt.set(i, debt.get(i) - debt.get(start));
  19.             }
  20.         return r;
  21.     }
复制代码

补充内容 (2018-10-3 01:18):
看懂了 dfs 的部分,原本一直誤會 A 可以 balance 所有相反符號的數值,但其實只能夠 balance 一個呀...
回复

使用道具 举报

🔗
 楼主| linnumberone 2018-10-2 12:29:33 | 只看该作者
全局:
肥宅快乐水 发表于 2018-10-2 12:26
这题我自己想了很久.. 没想明白..

看明白了我回你

我看了整整兩小時,找了各種資源也沒想明白
有人回覆真感動!謝謝 :)
回复

使用道具 举报

全局:
我大概看明白了.. 说一下自己的心路历程吧.

之前我想这道题的时候一直想不明白, 觉得应该是走一个dfs或者什么..

说起来真惭愧, 这个题显然是一个金融领域常见现象.. net settle就用central clearing, 是个非常常见的应用. 然而我并没有往这方面想.

我先看了一下你贴的代码, 想了一下为什么前面用map做. (暂时没考虑后面的settle 的dfs)

然后我就理解, 他是想把这个想成一个有中央清算功能的东西. 你这样想, 不论有谁给谁掏钱, 都假设他给了一个’银行’, 或者类似中介, 中转站这种.

然后不论谁收钱, 也都是从’银行’这里收钱.

那么一个人跟银行不交钱, 也不收钱(或者说balance = 0)的话, 那么这个人跟银行就是清的.

我
1) 第一个答案是这样考虑的. 假设有一个银行, 那么收钱/取钱(分别叫左边和右边) 的人就是最多的那笔交易.
这个答案有反例
[2,2,2], [5,1]这里是说左边有3笔,右边有2笔. 但需要4次交易才能清, 而不是3次. 因为[2,2,1] =[5], 然后 剩余的[1] = [1]

2) 这时我换了一个想法, 是把左边和右边分开放进两个pq, 从大到小greedy 做. 那么最大的先付最大的.
这里又有一个反例, 是如果有直接可以完成的交易, 应该提前做掉.
[6,5,4], [5,4,3,3]. 显然应该4次交易.  但是按greedy这个写法 , 就做不到5,4提前结束.

3) 现在我再换了一个想法, 提前把可以匹配的的答案去掉.
反例是[6,1,4], [3,3,5]. 这个是27/29, 已经非常接近答案了.

现在我就不知道该怎么做了.. 按这个尿性这个题只能枚举, 但是题里没有写交易一共多少笔, 也没说net之后又多少.. 如果必须枚举那应该小于15这样..

然后我看了你贴的settle这个函数, 就很好理解了.

先跳掉所有的balanced account, 即0.
然后dfs做, 相反符号才匹配. 这个很直观了.

{:8_249:}

评分

参与人数 1大米 +3 收起 理由
linnumberone + 3 謝謝!

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表