亚马逊网站 如何做站内seo,建站之星好不好,专业美工设计网站建设,网站系统繁忙是什么意思在一组 N 个人#xff08;编号为 0, 1, 2, …, N-1#xff09;中#xff0c;每个人都有不同数目的钱#xff0c;以及不同程度的安静#xff08;quietness#xff09;。
为了方便起见#xff0c;我们将编号为 x 的人简称为 person x 。
如果能够肯定 perso…在一组 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。
其他的答案也可以用类似的推理来解释。
代码
class Solution {int[] res;public int[] loudAndRich(int[][] richer, int[] quiet) {MapInteger,ListInteger mapnew HashMap();int nquiet.length;resnew int[n];Arrays.fill(res,n);for(int i0;in;i)map.put(i,new ArrayList());for(int[] r:richer)//邻接表map.get(r[1]).add(r[0]);for(int i0;in;i){res[i]loud(richer,quiet,map,i,i);}return res;}private int loud(int[][] richer, int[] quiet, MapInteger, ListInteger map, int cur,int min) { if(res[cur]!quiet.length) return res[cur] ;//已经搜索过了直接返回结果int cMincur;//当前子节点的最小值for(int next:map.get(cur)){int nloud(richer, quiet, map, next,cMin);if(quiet[n]quiet[cMin]) cMinn;}res[cur]cMin;if(quiet[cMin]quiet[min])//和父节点搜索得出的最小值比较mincMin;return min;}
}
