从喧闹与富有中搞懂搜索和拓扑

原创
2021/12/24 22:54
阅读数 144

前言

大家好我是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个人,不是谁跟谁关系都很好,有的私交不一定很深。

你是江苏某穷乡僻壤来的,为人很害羞不跟人说话,只跟省会南京的一个舍友聊天,南京舍友跟你说他是南京城里土著你就知道他比你有钱了……。南京舍友跟北京舍友聊天得知北京舍友四合院卧槽北京舍友有钱,南京舍友跟上海舍友聊天得知上海舍友有好几套房肯定比它有钱,但北上两舍友性格不合没聊过家里啥情况互相不敢猜测谁比谁有钱。

所以你们宿舍形成这样一个关系:

image-20211215224021137

但是这里面有两种评判标准构造这个逻辑,一个是比我穷,一个是比我有钱,究竟怎么使用我们继续看题意。

题目说每个人有个低调值(简单说啦),然后每个人要找到这个逻辑中比自己有钱(包括自己)最低调的人。

比我有钱的角度

如果从比我有钱角度出发, 那么每次都要进行搜索,根据这个顺序结构找到比我有钱的最低调的人,比如看最上面从你出发,找南京知道的最低调的有钱人。但是这个步骤使用搜索递归,这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源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
0 评论
0 收藏
0
分享
返回顶部
顶部