841. 钥匙和房间

题目:https://leetcode-cn.com/problems/keys-and-rooms/

代码:

class Solution {

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        //访问过的房间数组,下标代表房间号,值为true代表访问过
        boolean[] visit = new boolean[rooms.size()];
        //当前拥有的钥匙
        Stack<Integer> myKeys = new Stack<>();
        myKeys.push(0);
        //只要还有钥匙就去开房间
        while (!myKeys.isEmpty()) {
            Integer key = myKeys.pop();
            if (!visit[key]) {
                //房间没开过,取得房间内的钥匙,并标记当前房间被访问过
                myKeys.addAll(rooms.get(key));
                visit[key] = true;
            }
        }
        //根据题目要求,只要有一间房间没有访问过,就返回false
        for (int i = 0; i < visit.length; i++) {
            if (!visit[i]) {
                return false;
            }
        }
        return true;
    }

}

按照题目描述,定义一个boolean类型的数组visit代表房间的访问情况,然后定义一个栈myKeys来保存当前拥有的钥匙,只要还有钥匙就去开房间,开完就把钥匙丢弃,开完房间之后获取房间内的所有钥匙,并继续开门直到无钥匙可开。最终通过visit数组判断结果是true还是false。

支付宝搜索:344355 领取随机红包

如果文章对您有帮助,欢迎给作者打赏