Problema
In C++, RAII lega una risorsa alla durata di un oggetto: la risorsa viene rilasciata automaticamente quando l'oggetto esce dallo scope. Gli oggetti nello stesso scope vengono distrutti in ordine inverso rispetto a quello di creazione.
Elabora gli eventi nell'ordine:
{: entra in un nuovo scope interno.}: lascia lo scope corrente; ogni risorsa acquisita al suo interno viene rilasciata, prima la più recente.acquire <name>: crea una risorsa nello scope corrente.
Quando gli eventi finiscono, gli scope aperti rimanenti terminano dal più interno al più esterno (incluso lo scope esterno del programma), rilasciando le loro risorse nello stesso modo.
Implementa raii_release_order(events).
Input
events: Gli eventi. Le parentesi graffe sono bilanciate oppure lasciate aperte, e non vengono mai chiuse senza essere state aperte.
Output
Restituisci i nomi delle risorse nell'ordine in cui vengono rilasciate.
Vincoli
0 ≤ numero di eventi ≤ 100,000
I nomi hanno da 1 a 20 caratteri senza spazi
Esempi
Input:
events = ["acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"]
Output atteso:
expected = ["lock", "file", "log", "db"]Input:
std::vector<std::string> events = {"acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"};
Output atteso:
std::vector<std::string> expected = {"lock", "file", "log", "db"};Input:
string[] events = new string[] {"acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"};
Output atteso:
string[] expected = new string[] {"lock", "file", "log", "db"};Spiegazione
Uscire dallo scope interno rilascia lock poi file (prima il più recente). Alla fine lo scope esterno rilascia log poi db: ["lock", "file", "log", "db"].
Input:
events = ["{", "acquire a", "{", "acquire b"]
Output atteso:
expected = ["b", "a"]Input:
std::vector<std::string> events = {"{", "acquire a", "{", "acquire b"};
Output atteso:
std::vector<std::string> expected = {"b", "a"};Input:
string[] events = new string[] {"{", "acquire a", "{", "acquire b"};
Output atteso:
string[] expected = new string[] {"b", "a"};Spiegazione
Due scope sono ancora aperti alla fine: quello più interno rilascia b, poi quello successivo rilascia a: ["b", "a"].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Tieni uno stack di scope, ognuno con le sue risorse in ordine.
Suggerimento 2
Chiudere uno scope rilascia le sue risorse dalla più recente alla più vecchia.
Suggerimento 3
Alla fine chiudi tutti gli scope ancora aperti, partendo dal più interno.
Complessità attesa
tempo O(numero di eventi), spazio aggiuntivo O(numero di eventi)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.