泰国网站后缀,青海个人旅游网站建设,做3d兼职网站,活动宣传软文文章目录1. 题目2. 解题1. 题目
在一组 N 个人#xff08;编号为 0, 1, 2, ..., N-1#xff09;中#xff0c;每个人都有不同数目的钱#xff0c;以及不同程度的安静#xff08;quietness#xff09;。
为了方便起见#xff0c;我们将编号为 x 的人简称为 perso…
文章目录1. 题目2. 解题1. 题目
在一组 N 个人编号为 0, 1, 2, ..., N-1中每个人都有不同数目的钱以及不同程度的安静quietness。
为了方便起见我们将编号为 x 的人简称为 person x 。
如果能够肯定 person x 比 person y 更有钱的话我们会说 richer[i] [x, y] 。 注意 richer 可能只是有效观察的一个子集。
另外如果 person x 的安静程度为 q 我们会说 quiet[x] q 。
现在返回答案 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 3456 以及 7)
最安静(有较低安静值 quiet[x])的人是 person 7。其他的答案也可以用类似的推理来解释。提示
1 quiet.length N 500
0 quiet[i] N所有 quiet[i] 都不相同。
0 richer.length N * (N-1) / 2
0 richer[i][j] N
richer[i][0] ! richer[i][1]
richer[i] 都是不同的。
对 richer 的观察在逻辑上是一致的。来源力扣LeetCode 链接https://leetcode-cn.com/problems/loud-and-rich 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考图Graph–拓扑排序Topological Sorting
class Solution {
public:vectorint loudAndRich(vectorvectorint richer, vectorint quiet) {int n quiet.size();vectorvectorint g(n);//有向图,富的指向穷的vectorint indegree(n, 0);//入度for(auto r : richer){g[r[0]].push_back(r[1]);indegree[r[1]];}queueint q;//点的idvectorint ans(n, -1);for(int i 0; i n; i)ans[i] i;//初始化最安静的是自己for(int i 0; i n; i){if(indegree[i] 0){q.push(i);//最富裕的人入度为0}}while(!q.empty()){int id q.front();//人的idint q_val quiet[ans[id]];//到他这为止最安静的人的安静值q.pop();for(auto nt : g[id])//跟他连接的人比他穷{if(q_val quiet[ans[nt]])//比 nt 更安静的人是 ans[nt], 其安静值没有q_val小ans[nt] ans[id];if(--indegree[nt] 0)q.push(nt);}}return ans;}
};192 ms 33.1 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
