【数学归纳法】【位运算】【异或】3068最大节点价值之和

简介: 【数学归纳法】【位运算】【异或】3068最大节点价值之和

本文涉及知识点

数学归纳法 位运算 异或

LeetCode3068. 最大节点价值之和

给你一棵 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] ,并将它们的值更新为:

nums[u] = nums[u] XOR k

nums[v] = nums[v] XOR k

请你返回 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 构成一棵合法的树。

位运算

image.png

图论

树说明是连通的。树是无向连通无环图。

数学归纳法

一,节点a和b直接相连,根据题意,可以nums[a]和nums[b]分别⊕ \oplus k。

二,节点a b 通过p条变相连,a 和c通过p+1条边相连,且最后一条边是bc。如果能nums[a]和nums[b]分别⊕ \oplus k,其它节点不变。则可以nums[a]和nums[c]⊕ \oplus k,中间的节点不变。

分两步:

操作(a,b) 操作(b,c) ,由于nums[b] ⊕ \oplus k 两次,其值不变。

也就是 任意连通的节点都可以⊕ \oplus k,而不影响其它节点。

记录个节点⊕ \oplusk 的变化,如果变大的数量是偶数,全部变大;如果奇数,两种选择:

a,除最小的外,全部变大。

b,最小的减少最少的结合,余下的两两结合。

代码

class Solution {
public:
  long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
    vector<int> vAdd;
    for (const auto& n : nums) {
      vAdd.emplace_back((n ^ k) - n);
    }
    sort(vAdd.begin(), vAdd.end());
    long long llRet = std::accumulate(nums.begin(), nums.end(), 0LL);
    int index = std::upper_bound(vAdd.begin(), vAdd.end(), 0) - vAdd.begin();
    if (1 & (vAdd.size()-index)) {
      if ((index) && (vAdd[index] + vAdd[index - 1] >= 0)) {
        index--;
      }
      else {
        index++;
      }
    }
    llRet += std::accumulate(vAdd.begin()+ index, vAdd.end(), 0LL);
    return  llRet;
  }
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
    assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
    if (v1.size() != v2.size())
    {
        assert(false);
        return;
    }
    for (int i = 0; i < v1.size(); i++)
    {
        Assert(v1[i], v2[i]);
    }
}
int main()
{
  vector<int> nums;
  int k;
  vector<vector<int>> edges;
  {
    Solution sln;
    nums = { 1, 2, 1 }, k = 3;
    auto res = sln.maximumValueSum(nums, k,edges);
    Assert(6LL, res);
  }
  {
    Solution sln;
    nums = { 2,3 }, k = 7;
    auto res = sln.maximumValueSum(nums, k, edges);
    Assert(9LL, res);
  }
  {
    Solution sln;
    nums = { 7,7,7,7,7,7 }, k = 3;
    auto res = sln.maximumValueSum(nums, k, edges);
    Assert(42LL, res);
  }
}

2024年3月版

class Solution {
public:
  long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
    vector<int> v;
    for (const auto& n : nums)
    {
      v.emplace_back((n ^ k) - n);
    }
    long long llRet = std::accumulate(nums.begin(), nums.end(), 0LL);
    sort(v.begin(), v.end());
    while (v.size() >= 2)
    {
      long long cur = v.back() + v[v.size() - 2];
      if (cur <= 0)
      {
        break;
      }
      llRet += cur;
      v.pop_back();
      v.pop_back();
    }
    return llRet;
  }
};


我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境: VS2022 C++17

如无特殊说明,本算法用**C++**实现。

目录
打赏
0
0
0
0
36
分享
相关文章
基于OSS的EB级数据湖
数据湖无缝对接多种计算分析平台,对Hadoop生态支持良好,存储在数据湖中的数据可以直接对其进行数据分析、处理、查询,通过对数据深入挖掘与分析,洞察数据中蕴含的价值。
基于OSS的EB级数据湖
LangChain 构建问题之智能体协同中的决策机制的实现如何解决
LangChain 构建问题之智能体协同中的决策机制的实现如何解决
116 1
数据平衡与采样:使用 DataLoader 解决类别不平衡问题
【8月更文第29天】在机器学习项目中,类别不平衡问题非常常见,特别是在二分类或多分类任务中。当数据集中某个类别的样本远少于其他类别时,模型可能会偏向于预测样本数较多的类别,导致少数类别的预测性能较差。为了解决这个问题,可以采用不同的策略来平衡数据集,包括过采样(oversampling)、欠采样(undersampling)以及合成样本生成等方法。本文将介绍如何利用 PyTorch 的 `DataLoader` 来处理类别不平衡问题,并给出具体的代码示例。
2150 2
xenomai内核解析--双核系统调用(一)
本文介绍了Xenomai内核系统调用的实现,探讨了在Linux内核与Xenomai实时内核共存时,系统调用如何区分和交互。系统调用是用户空间与内核空间通信的关键,它提供了硬件抽象、系统稳定性、安全性和可移植性。在32位系统中,通过`int 0x80`指令触发,而在64位系统中,使用`syscall`指令。Xenomai通过I-pipe拦截系统调用,区分实时与非实时任务,并通过`cobalt_syscalls`表执行相应操作。文章还详细解析了系统调用表的生成和权限控制机制。
253 1
xenomai内核解析--双核系统调用(一)
Opencv(C++)学习系列---Laplacian拉普拉斯边缘检测算法
Opencv(C++)学习系列---Laplacian拉普拉斯边缘检测算法
670 0
SSL证书及重要性
SSL证书是保障网络数据安全的关键工具,通过加密通道保护信息传输,防止窃取或篡改。它分为DV、OV和EV三种验证等级,以及单域名、多域名和通配符类型。
210 0
数据挖掘实战:基于KMeans算法对超市客户进行聚类分群
数据挖掘实战:基于KMeans算法对超市客户进行聚类分群
2061 0
全面了解CPU Profiler:解读CPU性能分析工具的核心功能与用法
**==Traceview==** 是一个用于分析应用程序性能的工具,用来分析函数调用过程。 **==CPU Profiler==** 是 集成在Android Studio 3.2版本之后的Android Profiler工具当中,实时记录展示 App cpu消耗,用来替代Traceview。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问