LeetCode——喧闹和富有 C++

题目描述：

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

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);//记录是否为已经判断完成的元素，如果是的话变为truefor(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;}