Problem
Das Composite-Pattern behandelt einzelne Objekte und Gruppen von Objekten auf dieselbe Weise. Die Größe eines Ordners ist die Größe seiner eigenen Dateien plus die Größen von allem, was sich darin befindet, egal wie tief verschachtelt.
Es gibt n Elemente mit den Nummern 0 bis n − 1, die einen Baum bilden. parents[i] ist der Ordner, der Element i enthält, oder -1 für die Wurzel (genau ein Element). sizes[i] ist die Größe des eigenen Inhalts von Element i.
Implementiere composite_folder_sizes(parents, sizes).
Input
parents: Der Elternknoten jedes Elements.
sizes: Die Eigen-Größe jedes Elements.
Output
Gib für jedes Element seine Gesamtgröße zurück: seine eigene Größe plus die Gesamtgrößen aller seiner Kinder.
Einschränkungen
1 ≤ n ≤ 100,000
0 ≤ sizes[i] ≤ 10^9; parents beschreiben genau einen Baum
Beispiele
Eingabe:
sizes = [1, 2, 3, 4]
parents = [-1, 0, 0, 1]
Erwartete Ausgabe:
expected = [10, 6, 3, 4]Eingabe:
std::vector<long long> sizes = {1, 2, 3, 4};
std::vector<long long> parents = {-1, 0, 0, 1};
Erwartete Ausgabe:
std::vector<long long> expected = {10, 6, 3, 4};Eingabe:
long[] sizes = new long[] {1, 2, 3, 4};
long[] parents = new long[] {-1, 0, 0, 1};
Erwartete Ausgabe:
long[] expected = new long[] {10, 6, 3, 4};Erläuterung
Element 3 (Größe 4) liegt in Element 1, also hat Element 1 insgesamt 2 + 4 = 6. Die Wurzel enthält die Elemente 1 und 2: 1 + 6 + 3 = 10. Ergebnis: [10, 6, 3, 4].
Eingabe:
sizes = [5, 0, 7]
parents = [1, -1, 1]
Erwartete Ausgabe:
expected = [5, 12, 7]Eingabe:
std::vector<long long> sizes = {5, 0, 7};
std::vector<long long> parents = {1, -1, 1};
Erwartete Ausgabe:
std::vector<long long> expected = {5, 12, 7};Eingabe:
long[] sizes = new long[] {5, 0, 7};
long[] parents = new long[] {1, -1, 1};
Erwartete Ausgabe:
long[] expected = new long[] {5, 12, 7};Erläuterung
Die Wurzel ist Element 1 ohne eigenen Inhalt; sie enthält die Elemente 0 und 2: 0 + 5 + 7 = 12.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Die Summe eines Ordners ist seine eigene Größe plus die Summen seiner Kinder.
Hinweis 2
Verarbeite Kinder vor ihren Eltern, zum Beispiel in absteigender Tiefe.
Hinweis 3
Vermeide tiefe Rekursion bei langen Ketten; ein expliziter Stack oder eine Reihenfolge ist sicherer.
Erwartete Komplexität
Zeit O(n), zusätzlicher Speicher O(n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.