关键词：

文章目录

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

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

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. 可以到达所有点的最少点数目

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. 钥匙和房间

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;
    
;

leetcode刷题笔记-数据结构-day14(代码片段)

文章目录LeetCode刷题笔记-数据结构-day14155.最小栈1.题目描述2.解题思路3.代码1249.移除无效的括号1.题目描述2.解题思路3.代码1823.找出游戏的获胜者1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day14155.最小栈1.题目描述原题... 查看详情

leetcode刷题笔记-数据结构-day21(代码片段)

文章目录LeetCode刷题笔记-数据结构-day21451.根据字符出现频率排序1.题目2.解题思路3.代码973.最接近原点的K个点1.题目2.解题思路3.代码LeetCode刷题笔记-数据结构-day21451.根据字符出现频率排序1.题目原题链接：451.根据字符出现频... 查看详情

leetcode刷题笔记-数据结构-day21(代码片段)

文章目录LeetCode刷题笔记-数据结构-day21451.根据字符出现频率排序1.题目2.解题思路3.代码973.最接近原点的K个点1.题目2.解题思路3.代码LeetCode刷题笔记-数据结构-day21451.根据字符出现频率排序1.题目原题链接：451.根据字符出现频... 查看详情

leetcode刷题笔记-数据结构-day20(代码片段)

文章目录LeetCode刷题笔记-数据结构-day20215.数组中的第K个最大元素1.题目2.解题思路3.代码347.前K个高频元素1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day20215.数组中的第K个最大元素1.题目原题链接：215.数组中的第K个... 查看详情

leetcode刷题笔记-数据结构-day12(代码片段)

文章目录LeetCode刷题笔记-数据结构-day1224.两两交换链表中的节点1.题目描述2.解题思路3.代码707.设计链表1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day1224.两两交换链表中的节点1.题目描述原题链接：24.两两交换链表... 查看详情

leetcode刷题笔记-数据结构-day20(代码片段)

文章目录LeetCode刷题笔记-数据结构-day20215.数组中的第K个最大元素1.题目2.解题思路3.代码347.前K个高频元素1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day20215.数组中的第K个最大元素1.题目原题链接：215.数组中的第K个... 查看详情

leetcode刷题笔记-数据结构-day16(代码片段)

文章目录LeetCode刷题笔记-数据结构-day16199.二叉树的右视图1.题目描述2.解题思路3.代码113.路径总和II1.题目描述2.解题思路3.代码450.删除二叉搜索树中的节点1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day16199.二叉树的右视... 查看详情

leetcode刷题笔记-数据结构-day15(代码片段)

文章目录LeetCode刷题笔记-数据结构-day15108.将有序数组转换为二叉搜索树1.题目描述2.解题思路3.代码105.从前序与中序遍历序列构造二叉树1.题目描述2.解题思路3.代码103.二叉树的锯齿形层序遍历1.题目描述2.解题思路3.代码LeetCode刷... 查看详情

leetcode刷题笔记-数据结构-day6(代码片段)

文章目录LeetCode刷题笔记-数据结构-day6415.字符串相加1.题目描述2.解题思路3.代码409.最长回文串1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day6415.字符串相加1.题目描述原题链接：415.字符串相加2.解题思路直接套用大... 查看详情

leetcode刷题笔记-数据结构-day11(代码片段)

文章目录LeetCode刷题笔记-数据结构-day11160.相交链表1.题目描述2.解题思路3.代码82.删除排序链表中的重复元素II1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day11160.相交链表1.题目描述原题链接：160.相交链表2.解题思路... 查看详情

leetcode刷题笔记-数据结构-day18(代码片段)

文章目录LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述2.解题思路3.代码297.二叉树的序列化与反序列化1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述原题链接... 查看详情

leetcode刷题笔记-数据结构-day18(代码片段)

文章目录LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述2.解题思路3.代码297.二叉树的序列化与反序列化1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述原题链接... 查看详情

leetcode刷题笔记-数据结构-day18(代码片段)

文章目录LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述2.解题思路3.代码297.二叉树的序列化与反序列化1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述原题链接... 查看详情

leetcode刷题笔记-数据结构-day5(代码片段)

文章目录LeetCode刷题笔记-数据结构-day5334.递增的三元子序列1.题目描述2.解题思路3.代码238.除自身以外数组的乘积1.题目描述2.解题思路3.代码560.和为K的子数组1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day5334.递增的三元... 查看详情

leetcode刷题笔记-数据结构-day7(代码片段)

文章目录LeetCode刷题笔记-数据结构-day790.单词规律1.题目描述2.解题思路3.代码763.划分字母区间1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day790.单词规律1.题目描述原题链接：90.单词规律2.解题思路算法：哈希表... 查看详情

leetcode刷题笔记-数据结构-day9(代码片段)

文章目录LeetCode刷题笔记-数据结构-day9187.重复的DNA序列1.题目描述2.解题思路3.代码5.最长回文子串1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day9187.重复的DNA序列1.题目描述原题链接：87.重复的DNA序列2.解题思路算法&... 查看详情

leetcode刷题笔记-数据结构-day10(代码片段)

文章目录LeetCode刷题笔记-数据结构-day102.两数相加1.题目描述2.解题思路3.代码142.环形链表II1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day102.两数相加1.题目描述原题链接：2.两数相加2.解题思路直接模拟即可：从... 查看详情

leetcode刷题笔记-数据结构-day13(代码片段)

文章目录LeetCode刷题笔记-数据结构-day1325.K个一组翻转链表1.题目描述2.解题思路3.代码143.重排链表1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day1325.K个一组翻转链表1.题目描述原题链接：25.K个一组翻转链表2.解题思... 查看详情