समस्या
The composite pattern treats single objects and groups of objects the same way. A folder's size is its own files plus the sizes of everything inside it, however deep.
There are n items numbered 0 to n − 1 forming a tree. parents[i] is the folder that contains item i, or -1 for the root (exactly one item). sizes[i] is the size of item i's own content.
Implement composite_folder_sizes(parents, sizes).
इनपुट
parents: The parent of each item.
sizes: The own size of each item.
आउटपुट
Return, for every item, its total size: its own size plus the totals of all its children.
सीमाएँ
1 ≤ n ≤ 100,000
0 ≤ sizes[i] ≤ 10^9; parents एक ही ट्री बनाता है
उदाहरण
इनपुट:
sizes = [1, 2, 3, 4]
parents = [-1, 0, 0, 1]
अपेक्षित आउटपुट:
expected = [10, 6, 3, 4]इनपुट:
std::vector<long long> sizes = {1, 2, 3, 4};
std::vector<long long> parents = {-1, 0, 0, 1};
अपेक्षित आउटपुट:
std::vector<long long> expected = {10, 6, 3, 4};इनपुट:
long[] sizes = new long[] {1, 2, 3, 4};
long[] parents = new long[] {-1, 0, 0, 1};
अपेक्षित आउटपुट:
long[] expected = new long[] {10, 6, 3, 4};व्याख्या
Item 3 (size 4) item 1 के अंदर है, इसलिए item 1 का total 2 + 4 = 6 है। root में items 1 और 2 हैं: 1 + 6 + 3 = 10. Result: [10, 6, 3, 4].
इनपुट:
sizes = [5, 0, 7]
parents = [1, -1, 1]
अपेक्षित आउटपुट:
expected = [5, 12, 7]इनपुट:
std::vector<long long> sizes = {5, 0, 7};
std::vector<long long> parents = {1, -1, 1};
अपेक्षित आउटपुट:
std::vector<long long> expected = {5, 12, 7};इनपुट:
long[] sizes = new long[] {5, 0, 7};
long[] parents = new long[] {1, -1, 1};
अपेक्षित आउटपुट:
long[] expected = new long[] {5, 12, 7};व्याख्या
Root item 1 है और उसका अपना content नहीं है; इसमें items 0 और 2 हैं: 0 + 5 + 7 = 12.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
फ़ोल्डर का कुल उसका अपना आकार और उसके बच्चों के कुल का योग है।
संकेत 2
पैरेंट से पहले बच्चों को प्रोसेस करें, जैसे गहराई के घटते क्रम में।
संकेत 3
लंबी चेन पर गहरे रिकर्शन से बचें; साफ़ स्टैक या क्रम ज़्यादा सुरक्षित है।
अपेक्षित जटिलता
समय O(n), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।