标签： 图

LeetCode刷题【851】喧闹和富有

2022 年 6 月 30 日 / / 0 Comments

有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为 x 的人简称为 “person x “。

给你一个数组 richer ，其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有钱。另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值。richer 中所给出的数据 逻辑自洽（也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x 更有钱的情况 ）。

现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是，在所有拥有的钱肯定不少于 person x 的人中，person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。

 

示例 1：

输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
输出：[5,5,2,5,4,5,6,7]
解释： 
answer[0] = 5，
person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。
唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7，
但是目前还不清楚他是否比 person 0 更有钱。
answer[7] = 7，
在所有拥有的钱肯定不少于 person 7 的人中（这可能包括 person 3，4，5，6 以及 7），
最安静（有较低安静值 quiet[x]）的人是 person 7。
其他的答案也可以用类似的推理来解释。

示例 2：

输入：richer = [], quiet = [0]
输出：[0]
 

提示：

  • n == quiet.length
  • 1 <= n <= 500
  • 0 <= quiet[i] < n
  • quiet 的所有值 互不相同
  • 0 <= richer.length <= n * (n - 1) / 2
  • 0 <= ai, bi < n
  • ai != bi
  • richer 中的所有数对 互不相同
  • 对 richer 的观察在逻辑上是一致的
Related Topics
  • 深度优先搜索
  • 图
  • 拓扑排序
  • 数组

  • 👍 204
  • 👎 0

    • DFS，还可以再优化下

    1. 遍历int[][] richer数组，生成一个map，构建当前节点和比他小的person节点的关联关系
    2. 在遍历的过程中，同时知道了哪些节点没有比他大的节点，存放于HashSet<Integer> starter中
    3. 从starter遍历逐个进行DFS，利用int[] quiet数组中对应的喧嚣值往下深搜的时候代入更新到结果int[] ans数组中
    4. 由于在初始化的时候赋值了Arrays.fill(ans,501)每个值为501，所以如果当前喧嚣值比当前的ans[i]大或者等于的话就不用继续往下更新了
    5. 最终int[] ans数组中存的是当前对应的quiet值，又因为quiet 的所有值 互不相同所以根据反向映射关系重新赋值更新为对应的person
    6. 其实int[] ans中也可以一开始就存对应的person,不用最终再转换一遍，但是一开始用quiet来比较运算比较直观点，所以就先这么写了
    7. 最终结果返映射的时候，如果当前ans[i]依然等于501，说明这个点是独立的，不和其他点有相关联，那么对应依旧为quiet[i]
    8. int[] ans数组也可以一开始就等于int[] quiet数组，但是这样的话再dfs过程中判断大小的时候需要再借助其他手段判断是否需要再往下层更新

    代码

    class Solution {

//     richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]],
//     quiet = [3,2,5,4,6,1,7,0]
//        6    5
//        ↓  ↙
//    2   3  ←  4
//    ↓ ↙   ↘
//    1       7
//    ↓
//    0

    HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
    int[] ans;
    int[] quiet;
    int[] quietToPerson;

    public int[] loudAndRich(int[][] richer, int[] quiet) {
        this.quiet = quiet;
        ans = new int[quiet.length];
        Arrays.fill(ans,501);
        quietToPerson = new int[quiet.length];
        for (int i = 0; i < quiet.length; i++) {
            quietToPerson[quiet[i]] = i;
        }

        HashSet<Integer> starter = new HashSet<>();
        for (int[] ints : richer) {
            if (!map.containsKey(ints[0])){
                map.put(ints[0],new HashSet<>());
            }
            map.get(ints[0]).add(ints[1]);
            starter.remove(ints[1]);
            starter.add(ints[0]);
        }
        starter.forEach(i -> {
            dfs(i,quiet[i]);
        });

        for (int i = 0; i < ans.length; i++) {
            ans[i]= quietToPerson[ans[i]>500?quiet[i]:ans[i]];
        }
        return ans;
    }

    public void dfs(int num, int min){
        if (min > quiet[num]){
            min = quiet[num];
        }
        if (ans[num] > min){
            ans[num] = min;
        }else{
            return;
        }
        if (map.containsKey(num)){
            int finalMin = min;
            map.get(num).forEach(integer -> {
                dfs(integer, finalMin);
            });
        }
    }
}

    LeetCode刷题【797】所有可能的路径

    2021 年 8 月 25 日 / / 0 Comments

    给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

    二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。

    译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a 。

     

    示例 1：

    输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

    示例 2：

    输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

    示例 3：

    输入：graph = [[1],[]]
输出：[[0,1]]

    示例 4：

    输入：graph = [[1,2,3],[2],[3],[]]
输出：[[0,1,2,3],[0,2,3],[0,3]]

    示例 5：

    输入：graph = [[1,3],[2],[3],[]]
输出：[[0,1,2,3],[0,3]]

     

    提示：

    • n == graph.length
    • 2 <= n <= 15
    • 0 <= graph[i][j] < n
    • graph[i][j] != i（即，不存在自环）
    • graph[i] 中的所有元素 互不相同
    • 保证输入为 有向无环图（DAG）
    Related Topics
  • 深度优先搜索
  • 广度优先搜索
  • 图
  • 回溯

  • 👍 161
  • 👎 0

    • 题解

    8月25日每日一题

    有向，无环这两个输入参数的特性使得这题的难度直线下降，不用考虑访问到已访问过的节点，不要考虑进入环的可能性

    直接就根据入参重新构建一个反向的关系图，如，

    原本入参告诉了从0节点可以前往4,3,1节点，而新的图上0的位置记录的是可以到达0节点的上一个节点有哪些，0节点是初始出发节点，显然没有，不如换个终点4节点。

    可知，能到达4节点的上一个节点可能为【0,1,3】，0节点为初始节点，可以结束，1节点的上一个节点可能为【0】结束，3节点的上一个节点可能为【0,2】，2节点的上一个节点可能为【1】，1节点的上一个节点可能为【0】结束。

    class Solution {

    boolean[][] pathMap;
    List<List<Integer>> list;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int target = graph.length-1;
        list = new ArrayList<>();
        createMap(graph);
        List<Integer> ls = new ArrayList<>();
        ls.add(target);
        dfs(ls,target);
        return list;
    }

    public void dfs(List<Integer> visitList, int node){
        if (node == 0){
            list.add(new ArrayList<>(visitList));
            return;
        }
        if (pathMap[node].length > 0){
            for (int i = 0; i < pathMap[node].length; i++) {
                if (!pathMap[node][i])continue;
                visitList.add(0,i);
                dfs(visitList,i);
                visitList.remove(0);
            }
        }
    }


    public void createMap(int[][] graph){
        pathMap = new boolean[graph.length][graph.length];
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[i].length; j++) {
                pathMap[graph[i][j]][i] = true;
            }
        }
    }
}

    后续

    从上面的例子可以看到第一开始从4节点找到1节点，1节点的上一个节点可能为【0】结束，而2节点后来又找到了1节点，这边可以优化下，额外记录下能到达0节点的所有点的可能路径，假设一个完整的能到达0路径是【8,6,5,1,0】

    那么需要记录下 8经过【6,5,1,0】，6经过【5,1,0】，5经过【1,0】能到达0节点。

    这样在后面再次絮叨6、5、1这些节点的时候无需再次尝试计算能否到达0节点

    补充，大意了，直接从0节点开始搜索也是可以的，之所以想要反向搜索是想要从基础数据的层面来规避最后进入死胡同的情况，比如这样的情况

    【【1，2】，【】，【】】最终结果应当是到达2节点，但是0节点也可以到达1节点，1节点最后却不能达到2节点，构建反向的路径的时候可以直接规避掉从0节点开始搜索进入1节点的情况