Đề bài
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).
Input
parents: The parent of each item.
sizes: The own size of each item.
Output
Return, for every item, its total size: its own size plus the totals of all its children.
Ràng buộc
1 ≤ n ≤ 100,000
0 ≤ sizes[i] ≤ 10^9; parents describe a single tree
Ví dụ
Đầu vào:
sizes = [1, 2, 3, 4]
parents = [-1, 0, 0, 1]
Kết quả mong đợi:
expected = [10, 6, 3, 4]Đầu vào:
std::vector<long long> sizes = {1, 2, 3, 4};
std::vector<long long> parents = {-1, 0, 0, 1};
Kết quả mong đợi:
std::vector<long long> expected = {10, 6, 3, 4};Đầu vào:
long[] sizes = new long[] {1, 2, 3, 4};
long[] parents = new long[] {-1, 0, 0, 1};
Kết quả mong đợi:
long[] expected = new long[] {10, 6, 3, 4};Giải thích
Item 3 (size 4) is inside item 1, so item 1 totals 2 + 4 = 6. The root holds items 1 and 2: 1 + 6 + 3 = 10. Result: [10, 6, 3, 4].
Đầu vào:
sizes = [5, 0, 7]
parents = [1, -1, 1]
Kết quả mong đợi:
expected = [5, 12, 7]Đầu vào:
std::vector<long long> sizes = {5, 0, 7};
std::vector<long long> parents = {1, -1, 1};
Kết quả mong đợi:
std::vector<long long> expected = {5, 12, 7};Đầu vào:
long[] sizes = new long[] {5, 0, 7};
long[] parents = new long[] {1, -1, 1};
Kết quả mong đợi:
long[] expected = new long[] {5, 12, 7};Giải thích
The root is item 1 with no content of its own; it contains items 0 and 2: 0 + 5 + 7 = 12.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
A folder's total is its own size plus its children's totals.
Gợi ý 2
Process children before parents, for example in reverse depth order.
Gợi ý 3
Avoid deep recursion on long chains; an explicit stack or ordering is safer.
Độ phức tạp mong đợi
O(n) time, O(n) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.