2021.12.15 - 178.喧闹和富有

2021.12.15 - 178.喧闹和富有

文章目录

• 1. 题目
• 2. 思路
• • (1) DFS
• 3. 代码

1. 题目

2. 思路 (1) DFS

• 根据richer可以构建出有向无环图，从任意一点出发，所能到达的点都是比起始点富有的点。
• 每个点的默认答案是其本身，利用深度优先搜索遍历比其富有的点，若比其富有的点同时比其安静，则更新其答案。

3. 代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    private List[] list;
    private int[] res;
    private int[] quiet;

    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        list = new List[n];
        res = new int[n];
        this.quiet = quiet;
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }
        for (int[] ints : richer) {
            list[ints[1]].add(ints[0]);
        }
        Arrays.fill(res, -1);
        for (int i = 0; i < n; i++) {
            dfs(i);
        }
        return res;
    }

    private void dfs(int i) {
        if (res[i] != -1) {
            return;
        }
        res[i] = i;
        for (Integer j : list[i]) {
            dfs(j);
            if (quiet[res[j]] < quiet[res[i]]) {
                res[i] = res[j];
            }
        }
    }
}