3068.最大节点价值之和:脑筋急转弯+动态规划(O(1)空间)
【LetMeFly】3068.最大节点价值之和:脑筋急转弯+动态规划(O(1)空间)
力扣题目链接:https://leetcode.cn/problems/find-the-maximum-sum-of-node-values/
给你一棵 n
个节点的 无向 树,节点从 0
到 n - 1
编号。树以长度为 n - 1
下标从 0 开始的二维整数数组 edges
的形式给你,其中 edges[i] = [ui, vi]
表示树中节点 ui
和 vi
之间有一条边。同时给你一个 正 整数 k
和一个长度为 n
下标从 0 开始的 非负 整数数组 nums
,其中 nums[i]
表示节点 i
的 价值 。
Alice 想 最大化 树中所有节点价值之和。为了实现这一目标,Alice 可以执行以下操作 任意 次(包括 0 次):
- 选择连接节点
u
和v
的边[u, v]
,并将它们的值更新为:<ul> <li><code>nums[u] = nums[u] XOR k</code></li> <li><code>nums[v] = nums[v] XOR k</code></li> </ul> </li>
请你返回 Alice 通过执行以上操作 任意次 后,可以得到所有节点 价值之和 的 最大值 。
示例 1:
输入:nums = [1,2,1], k = 3, edges = [[0,1],[0,2]] 输出:6 解释:Alice 可以通过一次操作得到最大价值和 6 : - 选择边 [0,2] 。nums[0] 和 nums[2] 都变为:1 XOR 3 = 2 ,数组 nums 变为:[1,2,1] -> [2,2,2] 。 所有节点价值之和为 2 + 2 + 2 = 6 。 6 是可以得到最大的价值之和。
示例 2:
输入:nums = [2,3], k = 7, edges = [[0,1]] 输出:9 解释:Alice 可以通过一次操作得到最大和 9 : - 选择边 [0,1] 。nums[0] 变为:2 XOR 7 = 5 ,nums[1] 变为:3 XOR 7 = 4 ,数组 nums 变为:[2,3] -> [5,4] 。 所有节点价值之和为 5 + 4 = 9 。 9 是可以得到最大的价值之和。
示例 3:
输入:nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]] 输出:42 解释:Alice 不需要执行任何操作,就可以得到最大价值之和 42 。
提示:
2 <= n == nums.length <= 2 * 104
1 <= k <= 109
0 <= nums[i] <= 109
edges.length == n - 1
edges[i].length == 2
0 <= edges[i][0], edges[i][1] <= n - 1
- 输入保证
edges
构成一棵合法的树。
挺有意思的题
解题方法:动态规划
推导一
前提:
- 一个数异或$k$两次相当于没异或
- 选择树中一条路径上的所有边,相当于只有路径两端的两个元素异或了$k$(中间每个元素都会异或$k$两次)
- 树上任意两点之间存在一条路径
结论:
- 相当于我可以从$nums$数组中任选两个数异或,实际上我连边都有哪些都不用管,edges数组直接删!
推导二
前提:
每次操作都会作用两个数
- 如果操作前两个数都异或过,操作后相当于两个数都没异或过
- 如果操作前两个数都没异或过,操作后相当于两个数都异或过
- 如果操作前两个数一个异或过一个没异或过,操作后相当于两个数一个没异或过一个异过
结论:
- 无论操作多少次,都相当于有偶数个数被异或了
解题思路
我们可以使用动态规划数组$odd[i]$代表$nums$前$i$个数中有奇数个被异或过的元素最大和,$even[i]$代表$nums$前$i$个数中有偶数个被异或过的元素最大和。
对于一个数$nums[i]$,可以选择也可以不选,对应
$odd[i]=\max(odd[i]+nums[i], even[i]+(nums[i]\verb|^|k))$
$even[i]=\max(even[i]+nums[i], odd[i]+(nums[i]\verb|^|k))$
当然也可以原地滚动优化空间。
时空复杂度分析
- 时间复杂度$O(len(nums))$
- 空间复杂度$O(1)$
AC代码
C++
1 |
|
Python
1 |
|
Java
1 |
|
Go
1 |
|
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
3068.最大节点价值之和:脑筋急转弯+动态规划(O(1)空间)
https://blog.letmefly.xyz/2025/05/27/LeetCode 3068.最大节点价值之和/