本文主要是介绍Leetcode 2973. Find Number of Coins to Place in Tree Nodes,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
- Leetcode 2973. Find Number of Coins to Place in Tree Nodes
- 1. 解题思路
- 2. 代码实现
- 题目链接:2973. Find Number of Coins to Place in Tree Nodes
1. 解题思路
这道题思路上其实挺简单的,就是一个遍历的思路,找到每一个点对应的子树当中所有的节点,然后按照条件进行赋值即可。
不过,直接地实现会导致超时问题的问题,因此我们对此需要做一下剪枝,具体来说的话,由于我们要求取3个元素的最大乘积,因此考虑到正负性,选择上必然只有两种情况:
- 最大的三个元素
- 最大的一个元素与最小的两个元素
因此,我们事实上不需要保留全部的元素,只需要排序之后对每一个子树保留至多5个元素即可,从而大幅简化我们的存储还有排序复杂度。
2. 代码实现
给出python代码实现如下:
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,占用内存38.5MB。
这篇关于Leetcode 2973. Find Number of Coins to Place in Tree Nodes的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!