nginx反向代理 ssh命令 Ractivejs bootstrap模板 后台界面 easyui视频 js获取焦点事件 mysql安装后怎么使用 kb转mb matlab中axis webform开发教程 matlab取绝对值 android网络请求 数据库教程 python命令 python变量定义 python函数的调用 java8特性 java介绍 javaif语句 java学习文档 java的for循环 java获取当前线程 java索引 java基础框架 java连接sql java语言入门 java中的map java获取url参数 js四舍五入 onenote2003 volist 动态加载js 三维看图软件 飞猪ip php购物车 滑动门代码 mysql使用教程 字符串分割成数组 文章查重软件
当前位置: 首页 > 学习教程  > 编程语言

力扣之841. 钥匙和房间

2020/8/31 14:05:42 文章标签:

有 N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,…,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上,对于每个房间 i 都有一个钥匙列表 rooms[i],每个钥匙 rooms[i][j] 由 [0,1,…,N-1] 中的一个整数表示,其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初,除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true,否则返回 false。

示例 1:

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

示例 2:

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

提示:

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
所有房间中的钥匙数量总计不超过3000。

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function (rooms) {
    let set = new Set();
    for (let i = 1; i < rooms.length; i++) {
        set.add(i);
    }
    const dfs = (temp) => {
        for (let item of temp) {
            if (set.has(item)) {
                set.delete(item);
                dfs(rooms[item]);
            }
        }
    }
    dfs(rooms[0]);
    return set.size == 0;
};

自己写的算法永远不能优化时间和空间。


本文链接: http://www.dtmao.cc/news_show_150170.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?