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

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

1. 解題思路

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

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

1. 最大的三個(gè)元素
2. 最大的一個(gè)元素與最小的兩個(gè)元素

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

2. 代碼實(shí)現(xiàn)

給出python代碼實(shí)現(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

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