照片做视频ppt模板下载网站好,南京网站制作哪家好,网站建设银川,网站备案流程多少钱本文涉及知识点
C贪心 反证法 决策包容性 CDFS
LeetCode2673. 使二叉树所有路径值相等的最小代价
给你一个整数 n 表示一棵 满二叉树 里面节点的数目#xff0c;节点编号从 1 到 n 。根节点编号为 1 #xff0c;树中每个非叶子节点 i 都有两个孩子#xff0c;分别是左孩子…本文涉及知识点
C贪心 反证法 决策包容性 CDFS
LeetCode2673. 使二叉树所有路径值相等的最小代价
给你一个整数 n 表示一棵 满二叉树 里面节点的数目节点编号从 1 到 n 。根节点编号为 1 树中每个非叶子节点 i 都有两个孩子分别是左孩子 2 * i 和右孩子 2 * i 1 。 树中每个节点都有一个值用下标从 0 开始、长度为 n 的整数数组 cost 表示其中 cost[i] 是第 i 1 个节点的值。每次操作你可以将树中 任意 节点的值 增加 1 。你可以执行操作 任意 次。 你的目标是让根到每一个 叶子结点 的路径值相等。请你返回 最少 需要执行增加操作多少次。 注意 满二叉树 指的是一棵树它满足树中除了叶子节点外每个节点都恰好有 2 个子节点且所有叶子节点距离根节点距离相同。 路径值 指的是路径上所有节点的值之和。 示例 1 输入n 7, cost [1,5,2,2,3,3,1] 输出6 解释我们执行以下的增加操作
将节点 4 的值增加一次。将节点 3 的值增加三次。将节点 7 的值增加两次。 从根到叶子的每一条路径值都为 9 。 总共增加次数为 1 3 2 6 。 这是最小的答案。 示例 2
输入n 3, cost [5,3,3] 输出0 解释两条路径已经有相等的路径值所以不需要执行任何增加操作。 提示 3 n 105 n 1 是 2 的幂 cost.length n 1 cost[i] 104
C贪心
C贪心
两轮DFS 第一轮后序DFS求各子树最大路径和并保存令整棵树路径和的最大值iMax。return 当前节点的值 max(DFS1(左子树),DFS1(右子树)); 第二轮 前序DFS当前节点增加iMax - ( 当前节点的祖先节点和 本子树最大路径和) 性质一由于只能增加不能减少所以最终路径和一定大于等于iMax。 性质二路径和大于iMax一定不是最优解。如果路径和大于iMax说明所有路径都加了1每条路径都减少一个增加的1。如果一条路径有多个节点可以减减层次最小的根节点层次最小叶节点层次最大。从层次小的节点开始减。这样可以避免某条路径被减少了两次下面用反证法证明 令路径p1的节点n1已经减1给路径p2的节点n2减1的时候p1再次减一。 → \rightarrow → n1,n2都是p1的祖先n2包括p2,n1不包括。 → \rightarrow → n2的层次 n1的层次。与假设矛盾。 结论一最终路径和就是iMax。 如果某条路径需要增加则在保证不让其他路径超过iMax的情况下增加层次小的节点。这样可以让更多的路径增加。决策包容性 DFS2(cur,need) cur need - 当前子树最大路径值 DFS2(左子树,need-cur) DFS2(右子树,need-cur) 为了方便计算可以插入任意一个原始这样下标就从1开始。
代码
核心代码
class Solution {public:int minIncrements(int N, vectorint cost) {cost.insert(cost.begin(), 0);vectorint maxs(N 1);functionint(int) DFS1 [](int root) {if (root N) { return 0; }return maxs[root] cost[root] max(DFS1(root * 2), DFS1(root * 2 1));};const int iMax DFS1(1);int ans 0;functionvoid(int, int) DFS2 [](int root, int need) {if (root N) { return; }const int iAdd need - maxs[root];ans iAdd;DFS2(2 * root, need - iAdd - cost[root]);DFS2(2 * root 1, need - iAdd - cost[root]);};DFS2(1, iMax);return ans;} };单元测试
int n;vectorint cost;TEST_METHOD(TestMethod11){n 7, cost { 1, 5, 2, 2, 3, 3, 1 };auto res Solution().minIncrements(n, cost);AssertEx(6, res);}TEST_METHOD(TestMethod12){n 3, cost { 5,3,3 };auto res Solution().minIncrements(n, cost);AssertEx(0, res);}优化不需要DFS
任何叶子节点必须和兄弟节点相等否则这两条路径必定不等。 一将所有叶子节点增加到和他的兄弟节点相等。 二令当前树为cur将各左叶子加到父节节点。删除所有叶子节点形成新树next。cur符合题意 ⟺ \iff ⟺ next符合题意。 执行一二树的最大层次会减少1。不断执行直到树的层次为1结束。 无需DFS直接按节点编号从大到小执行。
class Solution {public:int minIncrements(int N, vectorint cost) {cost.insert(cost.begin(), 0);int ans 0;for (int i N; i 1; i-2 ) {const int iMin min(cost[i], cost[i - 1]);const int iMax max(cost[i], cost[i - 1]);ans iMax - iMin;cost[i / 2] iMax;}return ans;} };扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
