Problème
En C++, RAII lie une ressource à la durée de vie d'un objet : la ressource est libérée automatiquement quand l'objet sort de sa portée. Les objets d'une même portée sont détruits dans l'ordre inverse de leur création.
Traitez les événements dans l'ordre :
{: entre dans une nouvelle portée interne.}: quitte la portée courante ; chaque ressource acquise dedans est libérée, la plus récente d'abord.acquire <name>: crée une ressource dans la portée courante.
Quand il n'y a plus d'événements, les portées encore ouvertes se terminent de la plus interne à la plus externe (y compris la portée externe du programme) et libèrent leurs ressources de la même façon.
Implémentez raii_release_order(events).
Entrée
events: Les événements. Les accolades sont équilibrées ou restent ouvertes, jamais fermées sans avoir été ouvertes.
Sortie
Renvoyez les noms des ressources dans l'ordre de leur libération.
Contraintes
0 ≤ nombre d'événements ≤ 100,000
Les noms ont de 1 à 20 caractères sans espaces
Exemples
Entrée :
events = ["acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"]
Sortie attendue :
expected = ["lock", "file", "log", "db"]Entrée :
std::vector<std::string> events = {"acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"};
Sortie attendue :
std::vector<std::string> expected = {"lock", "file", "log", "db"};Entrée :
string[] events = new string[] {"acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"};
Sortie attendue :
string[] expected = new string[] {"lock", "file", "log", "db"};Explication
Quitter la portée interne libère lock puis file (la plus récente d'abord). À la fin, la portée externe libère log puis db : ["lock", "file", "log", "db"].
Entrée :
events = ["{", "acquire a", "{", "acquire b"]
Sortie attendue :
expected = ["b", "a"]Entrée :
std::vector<std::string> events = {"{", "acquire a", "{", "acquire b"};
Sortie attendue :
std::vector<std::string> expected = {"b", "a"};Entrée :
string[] events = new string[] {"{", "acquire a", "{", "acquire b"};
Sortie attendue :
string[] expected = new string[] {"b", "a"};Explication
Deux portées sont encore ouvertes à la fin : la plus interne libère b, puis la suivante libère a : ["b", "a"].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Gardez une pile de portées, chacune avec ses ressources dans l'ordre.
Indice 2
Fermer une portée libère ses ressources de la plus récente à la plus ancienne.
Indice 3
À la fin, fermez toutes les portées encore ouvertes, la plus interne d'abord.
Complexité attendue
temps O(nombre d'événements), espace supplémentaire O(nombre d'événements)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.