Giả sử chúng ta có một danh sách các số được gọi là nums. Danh sách này đại diện cho các nút lá trong đường đi ngang qua không gian của một cây. Ở đây các nút bên trong có 2 nút con và giá trị của chúng bằng tích của giá trị lá lớn nhất của cây con bên trái của nó và giá trị lá lớn nhất của cây con bên phải của nó. Chúng ta phải tìm tổng của cây với tổng các giá trị nhỏ nhất của nó
Vì vậy, nếu đầu vào là nums =[3, 5, 10], thì đầu ra sẽ là 83.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
- res:=tổng của tất cả các phần tử trong nums
- trong khi kích thước của nums> 1, thực hiện
- i:=chỉ số của phần tử tối thiểu của nums
- left:=nums [i - 1] khi i> 0, ngược lại là vô cực
- right:=nums [i + 1] khi tôi
- res:=res + (tối thiểu bên trái và bên phải) * phần tử thứ i trong số nums, sau đó xóa phần tử thứ i khỏi nums
- trả lại res
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Mã mẫu
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))
Đầu vào
[3, 5, 10]
Đầu ra
83