841. Keys and Rooms

LeetCode medium original: C# #array #csharp #leetcode #medium #stack

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

Есть n комнат, пронумерованных от 0 до n - 1, и все комнаты закрыты, кроме комнаты 0. Ваша цель — посетить все комнаты. Однако вы не можете войти в закрытую комнату, не имея ключа от нее.

Когда вы посещаете комнату, вы можете find в ней набор различных ключей. Каждый ключ имеет номер, указывающий, какую комнату он открывает, и вы можете взять их все с собой, чтобы открыть другие комнаты.

Дан tableau rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. return true, если вы можете посетить все комнаты, или false в противном случае.

Exemple:

Input: rooms = [[1],[2],[3],[]]

Output: true

Explanation:

We visit room 0 and pick up key 1.

We then visit room 1 and pick up key 2.

We then visit room 2 and pick up key 3.

We then visit room 3.

Since we were able to visit every room, we return true.

C# solution

correspondant/original

public class Solution {
    public bool CanVisitAllRooms(IList<IList<int>> rooms) {
        bool[] seen = new bool[rooms.Count];
        seen[0] = true;
        Stack<int> stack = new Stack<int>();
        stack.Push(0);
        while (stack.Count > 0) {
            int node = stack.Pop();
            foreach (int nei in rooms[node]) {
                if (!seen[nei]) {
                    seen[nei] = true;
                    stack.Push(nei);
                }
            }
        }
        foreach (bool v in seen) {
            if (!v) return false;
        }
        return true;
    }
}

C++ solution

brouillon automatique, à relire avant soumission

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool CanVisitAllRooms(IList<vector<int>> rooms) {
        bool[] seen = new bool[rooms.size()];
        seen[0] = true;
        stack<int> stack = new stack<int>();
        stack.push(0);
        while (stack.size() > 0) {
            int node = stack.pop();
            foreach (int nei in rooms[node]) {
                if (!seen[nei]) {
                    seen[nei] = true;
                    stack.push(nei);
                }
            }
        }
        foreach (bool v in seen) {
            if (!v) return false;
        }
        return true;
    }
}

Java solution

correspondant/original

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] seen = new boolean[rooms.size()];
        seen[0] = true;
        Stack<Integer> stack = new Stack();
        stack.push(0);

        while (!stack.isEmpty()) {
            int node = stack.pop();
            for (int nei: rooms.get(node))
                if (!seen[nei]) {
                    seen[nei] = true;
                    stack.push(nei);
                }
        }

        for (boolean v: seen)
            if (!v) return false;
        return true;
    }
}

JavaScript solution

correspondant/original

var canVisitAllRooms = function(rooms) {
    let seen = new Array(rooms.length).fill(false);
    seen[0] = true;
    let stack = [0];

    while (stack.length > 0) {
        let node = stack.pop();
        for (let nei of rooms[node]) {
            if (!seen[nei]) {
                seen[nei] = true;
                stack.push(nei);
            }
        }
    }

    return seen.every(Boolean);
};

Go solution

correspondant/original

func canVisitAllRooms(rooms [][]int) bool {
    seen := make([]bool, len(rooms))
    seen[0] = true
    stack := []int{0}

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        for _, nei := range rooms[node] {
            if !seen[nei] {
                seen[nei] = true
                stack = append(stack, nei)
            }
        }
    }

    for _, v := range seen {
        if !v {
            return false
        }
    }
    return true
}

Algorithm

Создайте tableau seen для отслеживания посещенных комнат и стек stack для ключей, которые нужно использовать.

Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную.

Пока стек не пуст, извлекайте ключи из стека и используйте их для открытия новых комнат, добавляя найденные ключи в стек. Если все комнаты посещены, return true, иначе false.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.