[LeetCode] 每日一题 2920. 收集所有金币可获得的最大积分
题目链接
题目描述
有一棵由 n
个节点组成的无向树,以 0
为根节点,节点编号从 0
到 n - 1
。给你一个长度为 n - 1
的二维 整数 数组 edges
,其中 edges[i] = [ai, bi]
表示在树上的节点 ai
和 bi
之间存在一条边。另给你一个下标从 0 开始、长度为 n
的数组 coins
和一个整数 k
,其中 coins[i]
表示节点 i
处的金币数量。
从根节点开始,你必须收集所有金币。要想收集节点上的金币,必须先收集该节点的祖先节点上的金币。
节点 i
上的金币可以用下述方法之一进行收集:
收集所有金币,得到共计
coins[i] - k
点积分。如果coins[i] - k
是负数,你将会失去abs(coins[i] - k)
点积分。收集所有金币,得到共计
floor(coins[i] / 2)
点积分。如果采用这种方法,节点i
子树中所有节点j
的金币数coins[j]
将会减少至floor(coins[j] / 2)
。
返回收集 所有 树节点的金币之后可以获得的最大积分。
示例输入
示例 1
输入:edges = [[0,1],[1,2],[2,3]], coins = [10,10,3,3], k = 5
输出:11
解释:
使用第一种方法收集节点 0 上的所有金币。总积分 = 10 - 5 = 5 。
使用第一种方法收集节点 1 上的所有金币。总积分 = 5 + (10 - 5) = 10 。
使用第二种方法收集节点 2 上的所有金币。所以节点 3 上的金币将会变为 floor(3 / 2) = 1 ,总积分 = 10 + floor(3 / 2) = 11 。
使用第二种方法收集节点 3 上的所有金币。总积分 = 11 + floor(1 / 2) = 11.
可以证明收集所有节点上的金币能获得的最大积分是 11 。
示例 2
输入:edges = [[0,1],[0,2]], coins = [8,4,4], k = 0
输出:16
解释:
使用第一种方法收集所有节点上的金币,因此,总积分 = (8 - 0) + (4 - 0) + (4 - 0) = 16 。
提示
n == coins.length
2 <= n <= 10^5
0 <= coins[i] <= 10^4
edges.length == n - 1
0 <= edges[i][0], edges[i][1] < n
0 <= k <= 10^4
解题思路
本题要求在树上收集金币,可以通过两种方式收集:一种是直接收集金币并扣除一个固定的积分,另一种是通过右移运算收集金币,但会影响子树中所有节点的金币数量。任务是求从根节点开始收集所有金币后能够获得的最大积分。
我们可以使用记忆化搜索来求解这个问题。具体做法是,递归地遍历树的每个节点,对于每个节点,有两种选择:不右移或者右移。通过状态记录来避免重复计算,保证高效性。记忆化搜索的状态由节点和当前右移的次数组成,避免了不必要的递归计算。
代码实现
class Solution {
public int maximumPoints(int[][] edges, int[] coins, int k) {
int n = coins.length;
List<Integer>[] graph = new ArrayList[n];
Arrays.setAll(graph, i -> new ArrayList<>());
// 构建无向图
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
graph[u].add(v);
graph[v].add(u);
}
int[][] memo = new int[n][14];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dfs(0, 0, -1, memo, graph, coins, k);
}
private int dfs(int node, int shiftCount, int parent, int[][] memo, List<Integer>[] graph, int[] coins, int k) {
// 如果该状态已经计算过,直接返回结果
if (memo[node][shiftCount] != -1) {
return memo[node][shiftCount];
}
// 当前节点不右移的积分
int noShiftPoints = (coins[node] >> shiftCount) - k;
// 当前节点右移一次的积分
int shiftPoints = coins[node] >> (shiftCount + 1);
for (int neighbor : graph[node]) {
if (neighbor == parent) continue;
// 递归计算不右移的积分
noShiftPoints += dfs(neighbor, shiftCount, node, memo, graph, coins, k);
// 递归计算右移的积分,前提是右移次数不超过限制
if (shiftCount < 13) {
shiftPoints += dfs(neighbor, shiftCount + 1, node, memo, graph, coins, k);
}
}
return memo[node][shiftCount] = Math.max(noShiftPoints, shiftPoints);
}
}
复杂度分析
时间复杂度:O(n * logU),其中 n 是节点数,U 是 coins 数组中金币的最大值。每个节点最多执行 logU 次右移操作,因此最多有 n * logU 次状态计算
空间复杂度:O(n * logU),需要一个二维数组
memo
来存储每个节点在不同右移次数下的计算结果,最多有 n * logU 个状态
总结
这道题通过树形结构和记忆化搜索结合的方式,解决了如何选择最优的方式收集金币的问题。通过判断当前节点选择右移还是不右移,并利用记忆化搜索避免重复计算,保证了高效性。
问题的关键在于如何合理地进行状态管理,并通过递归遍历树的每个节点,求出最大积分。通过优化的代码,我们可以确保即使在大数据量下也能高效计算出正确答案。
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。