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

淡淡的烟草味﹌ 2023-10-01 17:06 16阅读 0赞

#### 文章目录 ####

*  LeetCode刷题笔记-数据结构-day19
 *   *  997. 找到小镇的法官
     *   *  1.题目描述
         *  2.解题思路
         *  3.代码
     *  1557. 可以到达所有点的最少点数目
     *   *  1.题目描述
         *  2.解题思路
         *  3.代码
     *  841. 钥匙和房间
     *   *  1.题目描述
         *  2.解题思路
         *  3.代码

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

### 997. 找到小镇的法官 ###

#### 1.题目描述 ####

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

![image-20220202104902935][]

![image-20220202104910652][]

#### 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.代码 ####

class Solution {
        
    public:
        int findJudge(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. 可以到达所有点的最少点数目][1557.]

![image-20220202105728616][]

![image-20220202105743484][]

#### 2.解题思路 ####

题目的意思就是要我们求`入度`为`0`的点，直接模拟一遍即可。

具体步骤：

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

#### 3.代码 ####

class Solution {
        
    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. 钥匙和房间][841.]

![image-20220202111655330][]

![image-20220202111705950][]

#### 2.解题思路 ####

算法：`BFS`

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

#### 3.代码 ####

class Solution {
        
    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) return false;
            return true;
        }
    };

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16][]

[997.]: https://leetcode-cn.com/problems/find-the-town-judge/
[image-20220202104902935]: https://img-blog.csdnimg.cn/img_convert/9530a223ba827b9d4aa70bc0bc903c61.png
[image-20220202104910652]: https://img-blog.csdnimg.cn/img_convert/2c4785c85d74361fc278202e4b390a21.png
[1557.]: https://leetcode-cn.com/problems/minimum-number-of-vertices-to-reach-all-nodes/
[image-20220202105728616]: https://img-blog.csdnimg.cn/img_convert/74d8ab2fbfdcb8658f934c60d711dba0.png
[image-20220202105743484]: https://img-blog.csdnimg.cn/img_convert/4a29bae5738092c4ff5cf494d31d5900.png
[841.]: https://leetcode-cn.com/problems/keys-and-rooms/
[image-20220202111655330]: https://img-blog.csdnimg.cn/img_convert/f9b0a6db7fc49d9aed102a3939f8d378.png
[image-20220202111705950]: https://img-blog.csdnimg.cn/img_convert/0316386f0690a85fa7661d1461b6f9a5.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/26a973b4eb6243eba19b70c01a418799.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16