力扣每日一题2021-12-15喧嚣和富有

• 851.喧嚣和富有
• • 题目描述
  • 思路
  • • 记忆化+DFS
    • • Python实现
      • Java实现

喧嚣和富有

可以根据richer构建有向图，把人看成点，如果a比b有钱，则从b连一条有向边到a。因为是richer中的数据逻辑自恰，所以得到了一张有向无环图。
因此从图上任意一点出发，假设为x点，沿着有向边能访问到的点，都比x有钱。
因为题目要求计算的是钱不比x少的人中，最安静的人，因此可以分为钱数与x一样的人和钱数比x多的人两种类型。对于钱数一样的人，依据题意，只知道x有的钱与当前人相等，无法知道是否有其他人的钱与x相等。对于钱数比x多的人，可以先找出x的邻居的quiet值，取quiet值最小的为结果。综上两种情况，要么x本身最安静，要么x的某个邻居最安静。
计算x的邻居的quiet值是递归的过程，可以使用记忆化DFS实现。

class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        connect = defaultdict(set)
        for a,b in richer:
            connect[b].add(a)

        @lru_cache(None)
        def dfs(x):
            ans = x
            for other in connect[x]:
                if quiet[dfs(other)] < quiet[ans]:
                    ans = dfs(other)
            return ans

        return [dfs(i) for i in range(len(quiet))]

class Solution {
    private Map> connect;
    private int[] ans;
    private int[] quiet;
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        connect = new HashMap<>();
        ans = new int[quiet.length];
        this.quiet = quiet;
        for (int i = 0; i < quiet.length; i++) ans[i] = -1;
        for (int[] r: richer) {
            Set l = connect.getOrDefault(r[1], new HashSet<>());
            l.add(r[0]);
            connect.put(r[1], l);
        }
        for (int i = 0; i < quiet.length; i++) dfs(i);
        return ans;
    }
    private int dfs(int x) {
        if (ans[x] != -1) {
            return ans[x];
        }
        ans[x] = x;
        if (!connect.containsKey(x)) {
            return ans[x];
        }
        for (int other: connect.get(x)) {
            if (quiet[dfs(other)] < quiet[ans[x]]) {
                ans[x] = dfs(other);
            }
        }
        return ans[x];
    }
}