登录
  • #刷题

詢問 LC 465. Optimal Account Balancing

linnumberone
1883
5
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[[color=rgb(136, 0, 0)]0], m.getOrDefault(t[[color=rgb(136, 0, 0)]0], 0) - t[[color=rgb(136, 0, 0)]2]); m.put(t[[color=rgb(136, 0, 0)]1], m.getOrDefault(t[[color=rgb(136, 0, 0)]1], 0) + t[[color=rgb(136, 0, 0)]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; }
5条回复
热度排序

发表回复