LeetCode——喧闹和富有 C++_c++ 时间花费 金钱花费 leetcode

题目描述：

        本题依旧属于那种比较难理解但是较为好做的题目， 直接采用暴力方法遍历会超时。因此可以借助邻接矩阵来加速遍历流程。

vector<vector<int>>record(quiet.size(),vector<int>());

        在根据richer数组建立邻接矩阵后可以直接根据该邻接矩阵进行下一步判断，比如题目中的示例1按照元素数量生成的邻接矩阵为：{{0, 1}, {1, 2, 3}, {2}, {3, 4, 5, 6}, {4}, {5}, {6}, {7, 3}}，当该层中只有一个元素的时候，其最终的值就仅为该元素本身。之后根据已经判断完成的元素推出其他元素即可，比如编号3的矩阵{3, 4, 5, 6}中4,5,6三个元素都为确定的值，因此可以直接进行判断该矩阵的最终值。

        按照这个方法依次判断所有框中的最终值即可。

完整代码如下：

bool isok(vector<int>n,vector<bool>num1){//判断当前位置元素是否符合进入最终裁定标准
        for(int i=1;i<n.size();i++){
            if(!num1[n[i]])return false;
        }
        return true;
    }
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
        vector<vector<int>>record(quiet.size(),vector<int>());//邻接矩阵
        vector<int>num(quiet.size());//最终值
        vector<bool>num1(quiet.size(),false);//记录是否为已经判断完成的元素，如果是的话变为true
        for(int i=0;i<record.size();i++){
            record[i].push_back(i);
        }
        for(int i=0;i<richer.size();i++){//建立邻接矩阵
            record[richer[i][1]].push_back(richer[i][0]);
        }
        int n=0;//记录更改次数
        for(int i=0;i<num.size();i++){//初始化最终值
            if(record[i].size()==1){
                num[i]=i;
                num1[i]=true;
                n++;
            }
            num[i]=i;
        }
        while(n!=quiet.size()){//如果更改次数等于总数量，则程序运行完成返回num即可。
            for(int i=0;i<record.size();i++){
                if(!num1[i]&&isok(record[i],num1)){
                    num1[i]=true;
                    n++;
                    int min=1000;
                    for(int j=0;j<record[i].size();j++){
                        if(quiet[num[record[i][j]]]<min){
                            num[i]=num[record[i][j]];
                            min=quiet[num[record[i][j]]];
                        }
                    }
                }
            }
        }
        return num;
    }