邯郸网站建设优化,东莞市住房城乡建设网官网,广州手机网站开发,周口网站建设多少钱Leetcode 3068. Find the Maximum Sum of Node Values 1. 解题思路2. 代码实现 题目链接#xff1a;3068. Find the Maximum Sum of Node Values
1. 解题思路
这一题虽然标记为一道hard的题目#xff0c;但其实就是一个脑筋急转弯的题目。
我们只需要想明白一点即可…Leetcode 3068. Find the Maximum Sum of Node Values 1. 解题思路2. 代码实现 题目链接3068. Find the Maximum Sum of Node Values
1. 解题思路
这一题虽然标记为一道hard的题目但其实就是一个脑筋急转弯的题目。
我们只需要想明白一点即可
由于异或操作满足x^y^y x对于一棵联通树我们总可以通过有限次对相邻边地操作使得任意两点(u, v)转变为(u^z, v^z)而其他所有的节点都不发生变化。
因此我们只需要计算出所有点如果进行异或操作之后可以得到的改变量然后将其从大到小进行排序两两配对之后考察最大能够获得多少累积增长即可。
2. 代码实现
给出python代码实现如下
class Solution:def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) - int:delta sorted([(x ^ k) - x for i, x in enumerate(nums)], reverseTrue)i, n 0, len(delta)ans sum(nums)while i1 n and delta[i] delta[i1] 0:ans delta[i] delta[i1]i 2return ans提交代码评测得到耗时972ms占用内存28MB。
