千问 LeetCode 2973. 树中每个节点放置的金币数目 Go实现

以下是 LeetCode 2973. 树中每个放置的金币数目 的 Go 语言实现package mainimport (sort)func placedCoins(edges [][]int, cost []int) []int64 {n : len(cost)// 1. 建图 (邻接表)g : make([][]int, n)for _, edge : range edges {u, v : edge[0], edge[1]g[u] append(g[u], v)g[v] append(g[v], u)}ans : make([]int64, n)// 默认每个节点初始金币数为 1for i : range ans {ans[i] 1}// 2. 深度优先搜索var dfs func(node, fa int) []intdfs func(node, fa int) []int {// 收集当前子树的节点索引subtree : []int{node}for _, neighbor : range g[node] {if neighbor fa {continue // 无向树深搜防环跳过父节点}sub : dfs(neighbor, node)if len(sub) 5 {subtree append(subtree, sub...)} else {// 只保留2个最小的和3个最大的subtree append(subtree, sub[0], sub[1], sub[len(sub)-3], sub[len(sub)-2], sub[len(sub)-1])}}// 对当前子树的候选节点按 cost 排序sort.Slice(subtree, func(i, j int) bool {return cost[subtree[i]] cost[subtree[j]]})// 如果节点数大于5只保留极值if len(subtree) 5 {subtree []int{subtree[0], subtree[1],subtree[len(subtree)-3], subtree[len(subtree)-2], subtree[len(subtree)-1],}}// 计算当前节点应放置的金币数if len(subtree) 3 {sz : len(subtree)// 组合1: 两个最小的负数 * 最大的正数prod1 : int64(cost[subtree[0]]) * int64(cost[subtree[1]]) * int64(cost[subtree[sz-1]])// 组合2: 三个最大的正数prod2 : int64(cost[subtree[sz-3]]) * int64(cost[subtree[sz-2]]) * int64(cost[subtree[sz-1]])maxProd : prod1if prod2 maxProd {maxProd prod2}if maxProd 0 {ans[node] maxProd} else {ans[node] 0}}return subtree}dfs(0, -1)return ans}核心逻辑与 Go 语言特性说明1. 闭包与状态传递在 Go 中我们使用匿名函数 dfs 作为闭包这样可以直接访问外部的 cost 数组和 ans 结果数组避免了在函数参数中反复传递这些大数组代码更加简洁。2. 数学规律要在一个包含正负数的数组中选出3个数使乘积最大只有两种可能- 三个最大的正数- 一个最大的正数和两个最小的负数3. 剪枝优化基于上述规律我们在深度优先搜索DFS合并子树时不需要保留所有的节点。每个子树最多只需要保留 2个最小的 和 3个最大的 节点共5个即可。这大幅降低了存储和排序的复杂度使得时间复杂度维持在 O(N log N) 级别。4. 防环处理由于是无向树DFS 时需要传入父节点 fa遇到父节点直接跳过防止走回头路形成死循环。5. 结果计算当子树节点数不足3个时金币数保持初始值1当大于等于3个时取上述两种组合乘积的最大值若为负数则放置0个金币。注意 Go 中 int 的乘法可能会溢出计算乘积时使用了 int64 进行强转。