Problema
Il pattern composite tratta allo stesso modo oggetti singoli e gruppi di oggetti. La dimensione di una cartella è il contenuto proprio più le dimensioni di tutto ciò che contiene, a qualsiasi profondità.
Ci sono n elementi numerati da 0 a n − 1 che formano un albero. parents[i] è la cartella che contiene l'elemento i, oppure -1 per la radice (esattamente un elemento). sizes[i] è la dimensione del contenuto proprio dell'elemento i.
Implementa composite_folder_sizes(parents, sizes).
Input
parents: il genitore di ogni elemento.
sizes: la dimensione propria di ogni elemento.
Output
Restituisci, per ogni elemento, la sua dimensione totale: la dimensione propria più i totali di tutti i suoi figli.
Vincoli
1 ≤ n ≤ 100,000
0 ≤ sizes[i] ≤ 10^9; parents descrive un solo albero
Esempi
Input:
sizes = [1, 2, 3, 4]
parents = [-1, 0, 0, 1]
Output atteso:
expected = [10, 6, 3, 4]Input:
std::vector<long long> sizes = {1, 2, 3, 4};
std::vector<long long> parents = {-1, 0, 0, 1};
Output atteso:
std::vector<long long> expected = {10, 6, 3, 4};Input:
long[] sizes = new long[] {1, 2, 3, 4};
long[] parents = new long[] {-1, 0, 0, 1};
Output atteso:
long[] expected = new long[] {10, 6, 3, 4};Spiegazione
L'elemento 3 (dimensione 4) è dentro l'elemento 1, quindi l'elemento 1 vale 2 + 4 = 6. La radice contiene gli elementi 1 e 2: 1 + 6 + 3 = 10. Risultato: [10, 6, 3, 4].
Input:
sizes = [5, 0, 7]
parents = [1, -1, 1]
Output atteso:
expected = [5, 12, 7]Input:
std::vector<long long> sizes = {5, 0, 7};
std::vector<long long> parents = {1, -1, 1};
Output atteso:
std::vector<long long> expected = {5, 12, 7};Input:
long[] sizes = new long[] {5, 0, 7};
long[] parents = new long[] {1, -1, 1};
Output atteso:
long[] expected = new long[] {5, 12, 7};Spiegazione
La radice è l'elemento 1 senza contenuto proprio; contiene gli elementi 0 e 2: 0 + 5 + 7 = 12.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Il totale di una cartella è la sua dimensione più i totali dei figli.
Suggerimento 2
Elabora i figli prima dei genitori, per esempio per profondità decrescente.
Suggerimento 3
Evita la ricorsione profonda su catene lunghe; uno stack esplicito o un ordinamento è più sicuro.
Complessità attesa
tempo O(n), spazio aggiuntivo O(n)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.