• Leetcode 2973. Find Number of Coins to Place in Tree Nodes
  • 1. 解題思路
  • 2. 代碼實現(xiàn)

• 題目鏈接：2973. Find Number of Coins to Place in Tree Nodes

1. 解題思路

這道題思路上其實挺簡單的，就是一個遍歷的思路，找到每一個點對應(yīng)的子樹當(dāng)中所有的節(jié)點，然后按照條件進行賦值即可。

不過，直接地實現(xiàn)會導(dǎo)致超時問題的問題，因此我們對此需要做一下剪枝，具體來說的話，由于我們要求取3個元素的最大乘積，因此考慮到正負性，選擇上必然只有兩種情況：

1. 最大的三個元素
2. 最大的一個元素與最小的兩個元素

因此，我們事實上不需要保留全部的元素，只需要排序之后對每一個子樹保留至多5個元素即可，從而大幅簡化我們的存儲還有排序復(fù)雜度。

2. 代碼實現(xiàn)

給出python代碼實現(xiàn)如下：

class Solution:def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:n = len(cost)graph = defaultdict(list)for u, v in edges:graph[u].append(v)graph[v].append(u)tree = {}def dfs(root, parent):nonlocal treesubtree = [root]for node in graph[root]:if node == parent:continuesub = dfs(node, root)if len(sub) < 5:subtree.extend(sub)else:subtree.extend(sub[:2] + sub[-3:])subtree = sorted(subtree, key=lambda x: cost[x])tree[root] = subtreereturn subtreedfs(0, -1)ans = [1 for _ in range(n)]for i in range(n):subtree = tree[i]if len(subtree) < 3:continueans[i] = max(0, cost[subtree[0]] * cost[subtree[1]] * cost[subtree[-1]], cost[subtree[-1]] * cost[subtree[-2]] * cost[subtree[-3]])return ans

提交代碼評測得到：耗時1851ms，占用內(nèi)存38.5MB。