关注Java领域相关技术 记录有趣的事情

LeetCode-841. 钥匙和房间

US-B.Ralph
US-B.Ralph
2020-08-31

问题地址

LeetCode每日一题/2020-08-31

LeetCode841. 钥匙和房间


问题描述

规则

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. 1 <= rooms.length <= 1000
  2. 0 <= rooms[i].length <= 1000
  3. 所有房间中的钥匙数量总计不超过 3000。

解析

解题思路-死磕

从0号房间开始逐个开启房间,使用Map记录房间是否访问过,避免重复开启房间;
开启过程中只要Map中元素个数==给定房间的数量则返回true;
最终如果所有可以访问的房间中的钥匙均访问过但是Map中元素数量<给定房间数量则返回false;

复杂度分析

  1. 时间复杂度,O(n×m)。n为房间数量,m为房间中平均含有的钥匙数量。

  2. 空间复杂度,O(n)。记录访问过的房间。

定位问题

数据操作分析

  • 首先访问0号房间;
  • 如果0号房间中钥匙不为空,则遍历钥匙访问其他房间;
  • 访问过程中应避免重复访问,换房间或发现新钥匙可判断是否可以访问所有房间;

编码实现

/**
 * LeetCode841
 */
public class LeetCode841_KeysAndRooms {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        HashMap<Integer, Boolean> interviewEdRooms = new HashMap<>();
        //0号房不上锁
        interviewEdRooms.put(0, false);
        if (interviewEdRooms.size() == rooms.size()) return true;

        List<Integer> keys = rooms.get(0);
        if (keys == null || keys.isEmpty()) return false;

        Set<Integer> roomSet = interviewEdRooms.keySet();
        Iterator<Integer> iterator = roomSet.iterator();
        while (iterator.hasNext()) {
            Integer roomNo = iterator.next();
            if (!interviewEdRooms.get(roomNo)) {//只访问未进过的房间
                keys = rooms.get(roomNo);
                if (keys == null || keys.isEmpty()) continue;//没有钥匙就跳过
                for (int i = 0; i < keys.size(); i++) {
                    if (!interviewEdRooms.containsKey(keys.get(i))) {
                        interviewEdRooms.put(keys.get(i), false);
                        if (interviewEdRooms.size() == rooms.size()) return true;
                        roomSet = interviewEdRooms.keySet();
                        iterator = roomSet.iterator();
                    }
                }
            }
        }

        if (interviewEdRooms.size() == rooms.size()) return true;

        return false;
    }
}

解题思路-深度优先

从0号房间开始访问,当0号房有1、2、3号房间的钥匙时,我们可以自由地从0号房间进入1、2、3号房间;然后又可以自由地从1、2、3号房间分别进入它们所拥有钥匙的房间;

复杂度分析

  1. 时间复杂度,O(n+m)。n为房间数量,m为房间中的钥匙数量。

  2. 空间复杂度,O(n)。记录访问过的房间。

定位问题

数据操作分析

遍历当前所拥有的钥匙,统计可以到达的房间,并使用数组记录哪些房间访问过,避免重复访问;

编码实现

/**
 * LeetCode841
 */
public class LeetCode841_KeysAndRooms_dfs {
    boolean[] vis;//记录哪些房间是否访问过
    int visRoomCount;//记录访问了几间房间

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int roomCount = rooms.size();
        int roomNo = 0;//从0号房间开始访问
        vis = new boolean[roomNo];
        dfs(rooms, roomNo);
        return visRoomCount == roomCount;
    }

    private void dfs(List<List<Integer>> rooms, int roomNo) {
        vis[roomNo] = true;
        visRoomCount++;
        List<Integer> keys = rooms.get(roomNo);
        for (int i = 0; i < keys.size(); i++) {
            if (!vis[keys.get(i)]){
                dfs(rooms, keys.get(i));
            }
        }

    }
}

官方解法

深度优先搜索

思路:
  • 我们可以使用深度优先搜索的方式遍历整张图,统计可以到达的节点个数,并利用数组\textit{vis} 标记当前节点是否访问过,以防止重复访问。
复杂度分析:
  1. 时间复杂度,O(n+m)。n为房间数量,m为所有房间中的钥匙总数量。

  2. 空间复杂度,O(n)。其中 n 是房间的数量。主要为栈空间的开销。

class Solution {
    boolean[] vis;
    int num;

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        num = 0;
        vis = new boolean[n];
        dfs(rooms, 0);
        return num == n;
    }

    public void dfs(List<List<Integer>> rooms, int x) {
        vis[x] = true;
        num++;
        for (int it : rooms.get(x)) {
            if (!vis[it]) {
                dfs(rooms, it);
            }
        }
    }
}

广度优先搜索

思路
  • 我们也可以使用广度优先搜索的方式遍历整张图,统计可以到达的节点个数,并利用数组\textit{vis} 标记当前节点是否访问过,以防止重复访问。
复杂度分析:
  1. 时间复杂度,O(n+m)。n为房间数量,m为所有房间中的钥匙总数量。

  2. 空间复杂度,O(n)。其中 n 是房间的数量。主要为队列的开销。

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size(), num = 0;
        boolean[] vis = new boolean[n];
        Queue<Integer> que = new LinkedList<Integer>();
        vis[0] = true;
        que.offer(0);
        while (!que.isEmpty()) {
            int x = que.poll();
            num++;
            for (int it : rooms.get(x)) {
                if (!vis[it]) {
                    vis[it] = true;
                    que.offer(it);
                }
            }
        }
        return num == n;
    }
}
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

1 × 4 =