2021.12.15 力扣-每日一题-喧闹和富有

有一组 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] 最小的人）。

class Solution {
public:
    struct node
    {
        list nextnode;
    };
    vector loudAndRich(vector>& richer, vector& quiet) {
        int n = quiet.size();
        vector nodes(n);
        for (int i = 0; i < richer.size(); i++)
        {
            int a = richer[i][0];
            int b = richer[i][1];
            nodes[b].nextnode.push_back(a);
        }
        vector ans(n);
        for (int i = 0; i < n; i++)
        {
            int cur = quiet[i];
            int temp = i;
            queue que;
            set sets;
            que.push(i);
            sets.insert(i);
            while (!que.empty())
            {
                int k = que.front();
                que.pop();
                for (auto iter = nodes[k].nextnode.begin(); iter != nodes[k].nextnode.end(); iter++)
                {
                    if (cur > quiet[*iter])
                    {
                        cur = quiet[*iter];
                        temp = *iter;
                    }
                    if (!sets.count(*iter))
                    {
                        que.push(*iter);
                        sets.insert(*iter);
                    }
                }
            }
            ans[i] = temp;
        }
        return ans;
    }
};

又是一道阅读理解的题目，不过题目做多了也没那么难理解了，就是一个图的问题，看题解最优的是要用拓扑排序的方法， 不过我就直接暴力搜索了，还是复习数据库去吧。