851. Loud and Rich —— weekly contest 87

Stella981
• 阅读 791

851. Loud and Rich

题目链接:https://leetcode.com/problems/loud-and-rich/description/

思路:有向图DFS,记录最小的quiet值

注意点:可优化,记忆性搜索,每次搜到已经记录过的值时可直接比较不需要进一步搜下去。

 1 void DFS(vector<int> &visited, vector<vector<int> >& G, int x,vector<int>& quiet, int &res,int &minid){
 2         visited[x] = 1;
 3         if(res > quiet[x]){
 4             res = quiet[x];
 5             minid = x;
 6         }
 7         for(auto i:G[x]){
 8             if(visited[i] == 0){
 9                 DFS(visited,G,i,quiet,res,minid);
10             }
11         }
12         return;
13     }
14     vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
15         vector<int> ans;
16         int n = quiet.size();
17         vector<vector<int> > G;
18         G.resize(n);
19         for(auto i : richer){
20             G[i[1]].push_back(i[0]);
21         }
22         vector<int> visited;
23         
24         for(int i = 0 ; i < n; i++){
25             int res = 100000;
26             int minid = -1;
27             visited.assign(n,0);
28             DFS(visited,G,i,quiet,res,minid);
29             ans.push_back(minid);
30         }
31         return ans;
32     }
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解2016年09月02日00:00:36 \牧野(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fme.csdn.net%2Fdcrmg) 阅读数:59593
Stella981 Stella981
3年前
LeetCode——295. Find Median from Data Stream
一.题目链接:  https://leetcode.com/problems/findmedianfromdatastream(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fleetcode.com%2Fproblems%2Ffindmedianfromdatast
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
925. Long Pressed Name
题目链接:https://leetcode.com/problems/longpressedname/description/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fleetcode.com%2Fproblems%2Flongpressedname%2Fdescript
Stella981 Stella981
3年前
Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法
Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法参考文章:(1)Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.codeprj.com%2Fblo
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这