美文网首页
喧闹和富有

喧闹和富有

作者: xialu | 来源:发表于2021-12-15 23:44 被阅读0次

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/loud-and-rich

题目描述:

有一组 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]

代码实现:
class Solution {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        int[][] w = new int[n][n];
        int[] in = new int[n];
        for (int[] r : richer) {
            int a = r[0], b = r[1];
            w[a][b] = 1; in[b]++;
        }
        Deque<Integer> d = new ArrayDeque<>();
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = i;
            if (in[i] == 0) d.addLast(i);
        }
        while (!d.isEmpty()) {
            int t = d.pollFirst();
            for (int u = 0; u < n; u++) {
                if (w[t][u] == 1) {
                    if (quiet[ans[t]] < quiet[ans[u]]) ans[u] = ans[t];
                    if (--in[u] == 0) d.addLast(u);
                }
            }
        }
        return ans;
    }
}

相关文章

  • 喧闹和富有

    来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/loud-a...

  • 851. 喧闹和富有

    在一组 N 个人(编号为 0, 1, 2, ..., N-1)中,每个人都有不同数目的钱,以及不同程度的安静(qu...

  • 「算法」851. 喧闹和富有

    有一组 n 个人作为实验对象,从 0 到 n - 1 编号,其中每个人都有不同数目的钱,以及不同程度的安静值(qu...

  • 喧闹和宁静

    移动互联网时代,每个人都是一个巨大的 hub,大家每天都有可能接收到巨量的消息。一个几人的微信群,磕瓜子聊聊天就能...

  • 孤独和喧闹

    俞敏洪说 一个人的格局怎样,要看他孤独的时候在做什么。 牛逼的人们谁还没点奋斗的故事啊 让那些恐惧和孤独都他妈的见...

  • 远离喧闹和繁华

    我们去丽江吧 传说在彩云之南 有一个与世无争的地方 远离喧闹和繁华 可以治疗心灵的创伤 令人流连忘返 在丽江的某个...

  • 微醺

    破旧的一摇一晃的班车,富有热带气息的服饰和肤色,喧闹的环境,急速闪过的热带景色,马来西亚乡村里的班车!在热带乡村,...

  • 未雨

    大概天气已经入了伏,热气不停往房间里灌。 窗外是KTV 和麻将馆,喧闹难免。每天下午七点多还有广场舞,欢快而富有节...

  • 贫穷和富有

    到底何为贫穷何为富有,在大多数人眼里“钱”可能是衡量的标准,钱的多少决定了富足程度。 但是往往人们又忽略了另外一种...

  • 贫穷和富有

    在金钱的眼里 我从不曾富有 在时光的心中 我却从未贫穷 这样也好 我不必小心翼翼的 偷偷打开一条窗缝 偷窥日月 把...

网友评论

      本文标题:喧闹和富有

      本文链接:https://www.haomeiwen.com/subject/resmfrtx.html