LeetCode851 喧闹和富有

2023-11-10 17:40
文章标签 富有 喧闹 leetcode851

本文主要是介绍LeetCode851 喧闹和富有,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

851. 喧闹和富有icon-default.png?t=LA92https://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] 最小的人)。

咱们分析这道题,对每个人要找到比他有钱且最安静的人,首先自己的安静值是当前最小值,然后找出所有更有钱的人,找出这些人里安静值最小的加入answer,现在题目的核心在于:如何找出所有更有钱的人?很容易看出这是一个图论问题,方法有两种,第一种是DFS,注意这个图比较大,我们考虑记录每个人的目标是否计算出来,如果已计算则直接返回

class Solution {public int[] loudAndRich(int[][] richer, int[] quiet) {int n = quiet.length;//我们称对每个人来说,富有且更安静的人为“目标”//建立一张图,每个graph[i][j]意味着j比i更有钱//graph[i]存着所有比i更有钱的人List<Integer>[] graph = new List[n];for (int i = 0; i < n; ++i) {graph[i] = new ArrayList<Integer>();}for (int[] r : richer) {graph[r[1]].add(r[0]);}int[] ans = new int[n];//初始化为-1,如果不为零证明已经计算过,直接跳过Arrays.fill(ans, -1);//为每个人找到目标for (int i = 0; i < n; ++i) {dfs(i, quiet, graph, ans);}return ans;}//寻找x的目标public void dfs(int x, int[] quiet, List<Integer>[] graph, int[] ans) {if (ans[x] != -1) {return;}//初始的目标肯定是自己ans[x] = x;//遍历所有比x有钱的人for (int y : graph[x]) {//寻找所有更有钱的人你的目标//看看更富有的人的目标是否比我当前的目标更安静//如果更安静,那么我的目标更新dfs(y, quiet, graph, ans);if (quiet[ans[y]] < quiet[ans[x]]) {ans[x] = ans[y];}}}
}

方法二是拓扑排序,咱还没复习完,复习完回来补……

这篇关于LeetCode851 喧闹和富有的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/384247

相关文章

简单使用富有创造力的DALL·E 3 图像生成器——OpenAI Images Generations API

OpenAI Images Generations API 申请及使用 DALL-E 3 是 OpenAI 开发的两个版本的图像生成模型,它们能够根据文本描述生成高质量的图像。 本文档主要介绍 OpenAI Images Generations API 操作的使用流程,利用它我们可以轻松使用官方 OpenAI DALL-E 的图像生成功能。 申请流程 要使用 OpenAI Images G

读书 | 巴比伦最富有的人(内含思维导图)

《巴比伦最富有的人》这本书是在看《富爸爸与穷爸爸》这本书时,作者推荐的一本书,之前有个习惯就是看一本书,把书中推荐的书籍列成待读清单,也算是对广大书籍做一个筛选,遗憾的是之前记录下来后就没去看,近来重新捡起读书这项小事(很小的事却很难坚持)。 最近可以坚持下来是因为做了公众号,接触了身边公众号的朋友,都非常优秀,也明白一个道理:要输出(写文章),就需要有很多输入(学习),可能输入 100,

【AI论文与新生技术】Follow-Your-Emoji:精细可控且富有表现力的自由式人像动画技术

我们提出了 Follow-Your-Emoji,这是一种基于扩散的肖像动画框架,它使用目标地标序列对参考肖像进行动画处理。肖像动画的主要挑战是保留参考肖像的身份并将目标表情转移到该肖像,同时保持时间一致性和保真度。为了应对这些挑战,Follow-Your-Emoji 为强大的稳定扩散模型配备了两项精心设计的技术。 喜好儿网 具体来说,我们首先采用一种新的显式运动信号,即表情感知地标,来指导

1672. 最富有客户的资产总量 and 567. 字符串的排列

1672. 最富有客户的资产总量 题解一: 直接遍历,数组求和,一行代码搞定,不解释 class Solution:def maximumWealth(self, accounts: List[List[int]]) -> int:return max(sum(accounts[i]) for i in range(len(accounts))) 567. 字符串的排列

TypeScript算法每日一题:最富有客户的资产总量(1672)

作者:前端小王hs 阿里云社区博客专家/清华大学出版社签约作者✍/CSDN百万访问博主/B站千粉前端up主 题库:力扣 题目序号:1672(简单) 题目:最富有客户的资产总量 给你一个m x n的整数网格accounts,其中accounts[i][j]是第i​​​​​​​​​​​​位客户在第j家银行托管的资产数量。返回最富有客户所拥有的资产总量。 客户的资产总量就是他们在各家银行托管

AI图书推荐:ChatGPT全面指南—用AI帮你更健康、更富有、更智慧

你是否在努力改善你的健康? 你是否长期遭受财务困难? 你想丰富你的思想、身体和灵魂吗? 如果是这样,那么这本书就是为你准备的。 《ChatGPT全面指南—用AI帮你更健康、更富有、更智慧》(CHATGPT Chronicles AQuick Guide to Mastering Health, Wealthand Wisdom with Artificial Intelligence )涵

敏捷开发系列终极之旅 第六站(像橄榄球运动一样富有激情的SCRUM)

由来 为什么是Scrum?Scrum原本的意思是橄榄球运动的一个专业术语,指:“在橄榄球比赛中,双方前锋站在一起紧密相连,当球在他们之间投掷时他们奋力争球”。在敏捷开发系列中,把一种开发流程命名为Scrum,其实就意味着,这种敏捷开发的流程,就像是大家在一起打橄榄球,敏捷的动作、富有战斗的激情、人人你争我抢的拼搏精神。这些无一不是现在开发中迫切需要的东西。

(57)最富有客户的资产总量

文章目录 1. 每日一言2. 题目3. 解题思路3.1 法一3.2 法二 4. 代码4.1 法一4.2 法二 5. 结语 1. 每日一言 Care and diligence bring luck. 谨慎和勤奋,带来好运气。 2. 题目 题目链接:最富有客户的资产总量 给你一个 m x n 的整数网格 accounts ,其中 accounts[i][j] 是第 i

1672.最富有的客户的资产总量

刷算法题: 第一遍:1.看5分钟,没思路看题解 2.通过题解改进自己的解法,并且要写每行的注释以及自己的思路。 3.思考自己做到了题解的哪一步,下次怎么才能做对(总结方法) 4.整理到自己的自媒体平台。 5.再刷重复的类似的题目,根据时间和任务安排刷哪几个板块 6.用c++语言 都刷过一遍了 就刷中等 一.题目 给你一个 m x n 的整数网格 accounts ,其中 accou

全球最富有教授:大卫・切瑞顿 谷歌第一位投资人

加拿大人大卫・切瑞顿是斯坦福大学教授,教书之余,他还热衷于投资初创企业。一头黑白相间的鬈发,随意的牛仔裤和自己动手修剪的发型。即便在斯坦福大学校园里,大卫 切瑞顿教授都鲜为人知、至为低调。 到目前为止,切瑞顿仍然住在帕洛阿尔托的一处殖民地风格的房子,30 多年都没有换过。       在校的学生们很少意识到,这位导师竟然是全球最富有的教授。看起来他总是喜欢反复饮用茶包,而且开着一辆