สมมติว่าเรามีรายการหมายเลขที่เรียกว่า nums รายการนี้แสดงโหนดปลายสุดในการข้ามผ่านของต้นไม้ ที่นี่โหนดภายในมีลูก 2 คนและค่าของโหนดนั้นเหมือนกับผลคูณของค่าลีฟที่ใหญ่ที่สุดของทรีย่อยทางซ้าย และค่าลีฟที่ใหญ่ที่สุดของทรีย่อยทางขวา เราต้องหาผลรวมของต้นไม้ที่มีค่าผลรวมขั้นต่ำ
ดังนั้น หากอินพุตเป็น nums =[3, 5, 10] เอาต์พุตจะเป็น 83
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
- res :=ผลรวมขององค์ประกอบทั้งหมดเป็น nums
- ในขณะที่ขนาดของ nums> 1 ทำ
- i :=ดัชนีขององค์ประกอบขั้นต่ำของ nums
- ซ้าย :=nums[i - 1] เมื่อ i> 0 ไม่เช่นนั้นอินฟินิตี้
- right :=nums[i + 1] เมื่อ i
- res :=res + (ขั้นต่ำของซ้ายและขวา) * องค์ประกอบ ith ของ nums จากนั้นลบองค์ประกอบ ith ออกจาก nums
- ผลตอบแทน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
โค้ดตัวอย่าง
class Solution:
def solve(self, nums):
res = sum(nums)
while len(nums) > 1:
i = nums.index(min(nums))
left = nums[i - 1] if i > 0 else float("inf")
right = nums[i + 1] if i < len(nums) - 1 else float("inf")
res += min(left, right) * nums.pop(i)
return res
ob = Solution()
nums = [3, 5, 10]
print(ob.solve(nums)) อินพุต
[3, 5, 10]
ผลลัพธ์
83
