LeetCode刷题笔记-数据结构-day19

文章目录

LeetCode刷题笔记-数据结构-day19

997. 找到小镇的法官

1.题目描述

原题链接：997. 找到小镇的法官

2.解题思路

我们可以把每个人当做一个点，如果

a

信任

b

，则

a

的出度加

1

，

b

的入度加

1

。

我们可以直接用两个数组

dout[]

，

din[]

模拟每个点的出度和入度。

由题目的三个条件等价转换可得到，最终答案

x

需要满足：

1. 自己的出度为0，即dout[x]==0
2. 自己的入度为n-1，即din[x]==n-1
3. 只有一个小镇法官，如果最后出现了不止一个答案或者没有答案都要返回-1

3.代码

classSolution{public:intfindJudge(int n, vector<vector<int>>& v){
        vector<int>dout(n+1),din(n+1);for(auto x:v){
            dout[x[0]]++;
            din[x[1]]++;}int res=-1;for(int i=1;i<=n;i++)if(!dout[i]&&din[i]==n-1){if(res!=-1)return-1;
                res=i;}return res;}};

1557. 可以到达所有点的最少点数目

1.题目描述

原题链接：1557. 可以到达所有点的最少点数目

2.解题思路

题目的意思就是要我们求

入度

为

0

的点，直接模拟一遍即可。

具体步骤：

1. 第一次遍历，用一个bool数组或者set集合标识一个点有无入度
2. 第二次遍历，将没有入度的点加入答案即可

3.代码

classSolution{public:
    vector<int>findSmallestSetOfVertices(int n, vector<vector<int>>& edges){
        vector<bool>f(n);for(auto x:edges) f[x[1]]=true;
        vector<int> res;for(int i=0;i<n;i++)if(!f[i]) 
             res.push_back(i);return res;}};

841. 钥匙和房间

1.题目描述

原题链接：841. 钥匙和房间

2.解题思路

算法：

BFS

1. 将0号点加入队列，开始宽度优先遍历
2. 用一个bool数组表示该房间是否被打开过
3. 每进入一个房间，就遍历其中所有的钥匙。如果钥匙对应的房间已经进入过了，就不在入队列，否则入队
4. 最终队列为空表示没有其他可进的房间了
5. 最后遍历bool数组，判断是否有没进的房间，有返回false，没有返回true

3.代码

classSolution{public:
    bool canVisitAllRooms(vector<vector<int>>& v){int n=v.size();
        vector<bool>st(n,false);
        queue<int> q;
        q.push(0);
        st[0]=true;while(q.size()){int t=q.front();
            q.pop();for(auto x:v[t])if(!st[x]){
                    st[x]=true;
                    q.push(x);}}for(auto x:st)if(!x)returnfalse;returntrue;}};