前言
大家好我是bigsai。
今天给大家分享一个非常有趣的面试题,通过这个问题你可能会对某些情况下,搜索和拓扑有一定的认识,一个问题,既可以用搜索来处理,用记忆化搜索优化,也可以用拓扑排序来解决。
题目为力扣851,喧闹和富有 ,题意为
有一组 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] 最小的人)
理解题意
这个问题其实要理解题意还是需要一点时间的,我也读了不少时间才搞明白(原谅我语文很差)。
题目大概的意思是:题目告诉你一堆关系,对就是谁比谁有钱。
举个例子,你们宿舍4个人,不是谁跟谁关系都很好,有的私交不一定很深。
你是江苏某穷乡僻壤来的,为人很害羞不跟人说话,只跟省会南京的一个舍友聊天,南京舍友跟你说他是南京城里土著你就知道他比你有钱了……。南京舍友跟北京舍友聊天得知北京舍友四合院卧槽北京舍友有钱,南京舍友跟上海舍友聊天得知上海舍友有好几套房肯定比它有钱,但北上两舍友性格不合没聊过家里啥情况互相不敢猜测谁比谁有钱。
所以你们宿舍形成这样一个关系:
但是这里面有两种评判标准构造这个逻辑,一个是比我穷,一个是比我有钱,究竟怎么使用我们继续看题意。
题目说每个人有个低调值(简单说啦),然后每个人要找到这个逻辑中比自己有钱(包括自己)最低调的人。
比我有钱的角度
如果从比我有钱角度出发, 那么每次都要进行搜索,根据这个顺序结构找到比我有钱的最低调的人,比如看最上面从你出发,找南京知道的最低调的有钱人。但是这个步骤使用搜索递归,这4个人你看不出来,如果说你们宿舍5个人,有个山沟沟的舍友比你还穷,他搜索时候:你、南京舍友、{北京,上海搜索分叉}。然后到你的时候,又是:南京舍友、{北京,上海搜索分叉},这样重复计算效率很低啊。这就可以用记忆化搜索,搜过一遍记下来。
代码我没写,没用这个方法。因为搜索是从少的情况搜索更多未知的内容,会有比较多的重复计算,所以记忆化搜索就比较重要了。
比我穷的角度
从比我穷的角度来看,我是可以直接改变直接比我穷的那个人的低调值指向的,这个比我穷的角度就是拓扑排序了,例如上面北京舍友或者上海舍友肯定第一个。
假如北京舍友第一个,拓扑找到比我穷的南京舍友,然后看看我的低调值是不是比它的低,如果比他低,那么南京舍友低调值换成我的,并且低调指向编号是我。
然后上海舍友第二个,虽然你被北京舍友摩擦过但是不影响,上海舍友希望将南京舍友从北京小伙手中夺过来(有可能南京小伙本身非常低调没被感染),然后上海小伙三顾茅庐低调值比被感染过得南京舍友还低,那南京舍友还等什么,直接低调值跟随上海舍友,低调值指向上海舍友位置。
然后第三个南京舍友,他此时低调值非常低了(因为前面北上和他自己三个最低就是他),如果他低调值比你低,你低调值变成他一样,然后指向他指向的对应位置。
这就是一个拓扑排序的过程,这里面几个细节:
低调值改变:你可能直接支配比你穷的人,你一旦支配比你穷的,比你穷还穷的那些人很可能也被你支配,你的很低的低调值和位置需要被传递下去,所以需要一些标记。
附上代码:
class Solution {
public int[] loudAndRich(int[][] richer, int[] quiet) {
int len=quiet.length;
List<Integer> next[]=new ArrayList[len];//记录指向的集合
int inDegree[]=new int[len];//记录入度
int value[]=new int[len];
for(int i=0;i<len;i++){
next[i]=new ArrayList<>();
value[i]=i;
}
for(int i=0;i<richer.length;i++){
int rich=richer[i][0];
int poor=richer[i][1];
next[rich].add(poor);
inDegree[poor]++;
}
Queue<Integer>queue=new ArrayDeque<>();
for(int i=0;i<len;i++){
if(inDegree[i]==0)
queue.add(i);
}
while (!queue.isEmpty()){
int rich=queue.poll();
for(int poor:next[rich]){
inDegree[poor]--;
if(quiet[rich]<quiet[poor]){
quiet[poor]=quiet[rich];
value[poor]=value[rich];
}
if(inDegree[poor]==0){
queue.add(poor);
}
}
}
return value;
}
}
这样,这个问题就解决啦。
好啦,平安夜圣诞快乐,我是bigsai,我们下次再见!
本文同步分享在 博客“Big sai”(CSDN)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。