โจทย์
แพทเทิร์น composite ปฏิบัติกับออบเจกต์เดี่ยวและกลุ่มของออบเจกต์แบบเดียวกัน ขนาดของโฟลเดอร์คือเนื้อหาของตัวเองบวกขนาดของทุกอย่างที่อยู่ข้างใน ไม่ว่าจะลึกแค่ไหน
มี n รายการหมายเลข 0 ถึง n − 1 ซึ่งรวมกันเป็นต้นไม้ parents[i] คือโฟลเดอร์ที่บรรจุรายการ i หรือ -1 สำหรับราก (มีเพียงรายการเดียว) sizes[i] คือขนาดเนื้อหาของรายการ i เอง
จงเขียน composite_folder_sizes(parents, sizes)
อินพุต
parents: พาเรนต์ของแต่ละรายการ
sizes: ขนาดของแต่ละรายการเอง
เอาต์พุต
คืนขนาดรวมของทุกรายการ: ขนาดของตัวเองบวกขนาดรวมของลูกทั้งหมด
เงื่อนไข
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 มีผลรวมเป็น 2 + 4 = 6. รากมี items 1 และ 2: 1 + 6 + 3 = 10. ผลลัพธ์: [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};คำอธิบาย
รากคือ item 1 และไม่มีเนื้อหาของตัวเอง; มันมี items 0 และ 2 อยู่ภายใน: 0 + 5 + 7 = 12.
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ยอดรวมของโฟลเดอร์คือขนาดของตัวเองบวกยอดรวมของลูก
คำใบ้ 2
ประมวลผลลูกก่อนพาเรนต์ เช่น เรียงตามความลึกจากมากไปน้อย
คำใบ้ 3
เลี่ยงการเรียกซ้ำลึก ๆ บนสายยาว ใช้สแตกหรือลำดับที่ชัดเจนจะปลอดภัยกว่า
ความซับซ้อนที่คาดหวัง
เวลา O(n), หน่วยความจำเพิ่ม O(n)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน