LeetCode-841. 钥匙和房间

问题地址

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