• 题目描述:

  • 有一组 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] 最小的人)。

  • 示例:
    输入: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。
    其他的答案也可以用类似的推理来解释。

  • 解析,这个题目比较简单,很容易就想到这是一道考察深度优先遍历的题目,唯一的障碍在于我们需要自己构建图,然后基于构建的图来进行深度优先遍历,在遍历的过程中完成最安静的人的寻找。

  • 代码如下,主要分为两个部分,第一个部分是构建图,第二个部分是深度优先遍历。关于递归(深度优先遍历),不一定非要完全理解全过程,只需要理清跳出条件、递归公式这两个部分即可。以本题为例,加入我们有7个人,假如有一条路径1-3-5,我们可以完全想到那么遍历完这条路径,我们便可以为result[1, 3, 5]赋值,之后便不再需要进入这条路径,所以跳出条件应该是当前result[i]已经完成了赋值,递归公式就简单了,假设我们根据richer得到了graph[0]=[1], graph[1]=[2],那么每次的递归就是for y in graph[x],x的递归顺序是0-1-2,到这里递归的主体就完成了,接下来就是一个简单的if判断语句的嵌入,由于我们是一直递归到最深的地方才开始进行比较,因为最安静的人需要往后传递,即对路径1-3-5,ans[5]=5,ans[3]=5,ans[1]=5,因此这个判断语句肯定需要在递归语句后面。

class Solution:def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:"""给定richer和quite,返回返回一个整数数组 answer 作为答案,其中 answer[x] = y 的前提是,在所有拥有的钱肯定不少于 person x 的人中,person y 是最安静的人(也就是安静值 quiet[y] 最小的人)>>>richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]]>>>quiet = [3,2,5,4,6,1,7,0]>>>self.loudAndRich(richer, quiet)>>>[5,5,2,5,4,5,6,7]"""n = len(quiet)ans = [-1]*n#构建图graph = [[] for _ in range(n)]for route in richer:graph[route[1]].append(route[0])#深度优先遍历def dfs(x):if ans[x] != -1:return ans[x] = xfor y in graph[x]:dfs(y)if quiet[ans[y]] < quiet[ans[x]]:ans[x] = ans[y]#启动递归赋值for i in range(n):dfs(i)return ans

leetcode刷题日记-喧闹和富有相关推荐

  1. 一个算法笨蛋的12月leetCode刷题日记

    类似文章 一个算法笨蛋的2021年11月leetCode刷题日记 一个算法笨蛋的2021年12月leetCode刷题日记 一个算法笨蛋的2022年1月leetCode刷题日记 一个算法笨蛋的2022年 ...

  2. Leetcode刷题日记(十二)

    又是老台词:欢迎大家来到一晚一度的leetcode刷题日记时间.今天我们来讲讲队列的问题,队列这方面的基础知识需要的同学到博主前面的文章找吧.队列这方面的问题平时博主也是接触得比较少的.下面是一道利用 ...

  3. Leetcode刷题日记:21-25题篇

    Leetcode刷题日记:21-25题篇 简介 题目: 21. 合并两个有序链表 22. 括号生成 23. 合并K个升序链表 24. 两两交换链表中的节点 25. K 个一组翻转链表 注 简介 这个系 ...

  4. 【LeetCode刷题日记】常用算法基础和理解及运用

    在我们LeetCode刷题过程中,如果我们只是了解数据结构(数组,链表,数)的使用方法,那我们在面对复杂的题目时,是很难很好的解决问题的,因此我们要了解一些常用算法来帮助我们更好的解题. 递归和迭代 ...

  5. leetcode刷题日记(一)—— 数组

    因为暑期实习找得很不顺利,感觉自身最大的问题体现在刷题量偏少,操作系统,数据库基础不好,所以现在决定写博客来记录整个过程,希望能找到大厂offer,如果不能找到的话也算是为秋招做准备. 剑指offer ...

  6. [东哥的leetcode刷题日记] leetcode 278 :First Bad Version

    leetcode 278 :First Bad Version 题目链接: https://leetcode-cn.com/problems/search-insert-position/ 难度: 简 ...

  7. LeetCode刷题日记盛最多水的容器

    节后第一天,鉴于五一五天都没做过题,有点遗忘了,今天来看一道简单点的题,练下手. 先看下题: 给你 n 个非负整数 a1,a2,-,an,每个数代表坐标中的一个点 (i, ai) .在坐标内画 n 条 ...

  8. 石器时代 —— Leetcode刷题日记 (一 百大热题)

    Date: 2019.10.22 - (C++ Version) 文章目录 All Labels: `热题100` L1 两数之和 L2 两数相加 暴力相加 递归 迭代 L3 无重复字符的最长子串 L ...

  9. [东哥的leetcode刷题日记] leetcode 283 : Move Zeroes

    leetcode 283 : Move Zeroes 题目链接: https://leetcode-cn.com/problems/move-zeroes/ 难度: 简单 归类 : 数组操作 题目: ...

  10. LeetCode刷题日记精选例题(解析+代码+链接)

    文章目录 一.用栈模拟队列 二.用队列模拟栈 三.有效的括号 解法一 解法二 四.删除字符串中所有相邻重复项 五.逆波兰表达式求值 六.滑动窗口最大值 七.前k个高频元素 一.用栈模拟队列 因为队列先 ...

最新文章

  1. [转] 利用jemalloc分析内存泄漏
  2. JAVA中常见的Exception
  3. hadoop-16-sqoop导入oracle数据
  4. what format should you export from matlab?
  5. ArcGis中空间连接join
  6. [译]RabbitMQ教程C#版 - 发布订阅
  7. python web框架 - Django
  8. android canvas_Android实现自定义阴影效果
  9. ADO.NET Entity Framework(3)ObjectContext
  10. 云起智慧中心连接华为_云起荣获CIBIS十大全屋智能品牌奖:将与合作伙伴共同扩展AIoT生态平台...
  11. 美通社企业新闻汇总 | 2019.2.20 | 华为云新加坡大区开服;默克就提高CRISPR基因组编辑方法获首个美国专利...
  12. 想知道电脑上怎么压缩图片?用这3个方法实现快速压缩
  13. JAVA定义矩形类 方法一
  14. ERA5再分析资料下载攻略
  15. java毕业设计数码产品导购网站mybatis+源码+调试部署+系统+数据库+lw
  16. python中断输入_在 Python 中接管键盘中断信号的实现方法
  17. antd日期选择组件a-range-picker默认选中的时分秒
  18. java中文逗号替换成英文逗号_word如何将大量英文逗号批量替换为中文逗号?
  19. UEBA架构设计之路1
  20. 文员应该要学计算机哪些内容,文员的基本电脑知识是什么? 文员的基本要求有哪些?...

热门文章

  1. linux创建进程 api,.net Core 3.0 WebApi 创建Linux守护进程的方法
  2. java图形化元件竖直排列_Java:图形化比较排序
  3. php mysql delimiter,MySql delimiter的作用是什么_MySQL
  4. faster rcnn第二阶段loss出现nan_深度学习训练Loss异常Debug思路
  5. 大数据Hadoop学习记录(1)----HDFS目录和文件Shell操作
  6. 德国Java工程师_1886年,德国工程师。
  7. HighCharts:设置饼图图例文字颜色
  8. Swiper:基础学习
  9. 面向对象(Python):学习笔记之模块和包
  10. C++_弱引用 强引用_weak_ptr/share_ptr