首页 > 其他分享 >LeetCode.钥匙和房间

LeetCode.钥匙和房间

时间:2023-08-22 17:04:29浏览次数:55  
标签:房间 boolean 钥匙 rooms visited true LeetCode

1.代码:

有 n 个房间,房间按从 0 到 n - 1 编号。最初,除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而,你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间,你可能会在里面找到一套不同的钥匙,每把钥匙上都有对应的房间号,即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true,否则返回 false

 https://leetcode.cn/problems/keys-and-rooms/description/

示例 1:

输入:rooms = [[1],[2],[3],[]]
输出:true
解释:
我们从 0 号房间开始,拿到钥匙 1。
之后我们去 1 号房间,拿到钥匙 2。
然后我们去 2 号房间,拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间,我们返回 true。

示例 2:

输入:rooms = [[1,3],[3,0,1],[2],[0]]
输出:false
解释:我们不能进入 2 号房间。


2.代码:

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] visited = new boolean[rooms.size()];//一个数组来标记这个房间有没有被进入过
        dfs(0,rooms,visited);//深搜
        for(boolean result : visited){
            if(result==false) return false;//如果有没有进入过的房间,就返回false
        }
        return true;//否则就返回true
    }
    public void dfs(int key,List<List<Integer>> rooms,boolean[] visited){
        if(visited[key]==true) return;//这个房间已经进入过就跳过
        visited[key]=true;//否则就标记为进入过
        for(int i:rooms.get(key)){//这里是进入拿到了钥匙的对于的房间
           dfs(i,rooms,visited);
        }
    }
}





标签:房间,boolean,钥匙,rooms,visited,true,LeetCode
From: https://blog.51cto.com/u_15806469/7191231

相关文章

  • Leetcode 两个队列实现栈 swift
    queue1 是最后生成的栈queue2是临时队列,把新进来的先放进去,再把queue1里的数据从头到尾读进去,然后互换classMyStack{varqueue1:[Int]=[]varqueue2:[Int]=[]init(){}funcpush(_x:Int){queue2.append(x)whil......
  • LeetCode338.比特位计数
    先以2,3为例,它们的二进制分别是10、11,可以看到,忽略其二进制中最高位的1之后,这组数中二进制位为1的数量分别和数字0,1中二进制位为1的数量相同,再以4,5,6,7为例,他们的二进制分别是100、101、110、111,忽略其二进制中最高位的1之后,这组数中二进制位为1的数量分别和数字0,1,2,3中二进制位为1的......
  • LeetCode-164. 最大间距(Java)
    一、前言......
  • Leetcode 59. 螺旋矩阵 II && 剑指 Offer 29. 顺时针打印矩阵
    这两个题非常相似,但是前者较为简单,后者较难。由于前者访问的矩阵是方阵,因此可以通过迭代去做(因为方阵每次迭代,长和宽缩水的大小是一样的,但是矩阵不可以,因为矩阵最后一次迭代,长和宽的缩水不一定一样)classSolution{public:vector<vector<int>>generateMatrix(intn){......
  • Leetcode 242. 有效的字母异位词(Valid anagram)
    题目链接......
  • #yyds干货盘点# LeetCode程序员面试金典:完全二叉树的节点个数
    题目:给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。 示例1:输入:r......
  • LeetCode 周赛上分之旅 #40 结合特征压缩的数位 DP 问题
    ⭐️本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]和BaguTreePro知识星球提问。学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场LeetCode周赛的解题报告,一......
  • LeetCode 417.太平洋大西洋水流问题
    1.题目:https://leetcode.cn/problems/pacific-atlantic-water-flow/description/有一个 m×n 的矩形岛屿,与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界,而 “大西洋” 处于大陆的右边界和下边界。这个岛被分割成一个由若干方形单元格组成的网格。给......
  • LeetCode -- 第 359 场周赛
    本题我们只需要将所有首字母取出来,并与s比较即可。classSolution{public:boolisAcronym(vector<string>&words,strings){stringres;for(auto&it:words){res+=it[0];}returnres==s;}};  ......
  • IDEA 刷题工具 leetcode editor
    突然有一天不好用了,然后抓取新的cookie后也登陆不上https://github.com/shuzijun/leetcode-editor/issues/402之前的IDEA版本太低了,不支持JCEF更新到最新的2023.2版本但是又有了新的问题,发现evalreset用不了了,会抛出异常最后选择升级到2020.2.4版本的IDEA,解......