当前位置: 首页 > news >正文

【C++贪心 DFS】2673. 使二叉树所有路径值相等的最小代价|1917

本文涉及知识点

C++贪心 反证法 决策包容性
C++DFS

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, vector<int>& cost) {cost.insert(cost.begin(), 0);vector<int> maxs(N + 1);function<int(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;function<void(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;vector<int> 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, vector<int>& 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 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:

【C++贪心 DFS】2673. 使二叉树所有路径值相等的最小代价|1917

本文涉及知识点 C贪心 反证法 决策包容性 CDFS LeetCode2673. 使二叉树所有路径值相等的最小代价 给你一个整数 n 表示一棵 满二叉树 里面节点的数目&#xff0c;节点编号从 1 到 n 。根节点编号为 1 &#xff0c;树中每个非叶子节点 i 都有两个孩子&#xff0c;分别是左孩子…...

虚幻引擎GAS入门学习笔记(一)

虚幻引擎GAS入门(一) Gameplay Ability System&#xff08;GAS&#xff09; 是一个模块化且强大的框架&#xff0c;用于管理虚幻引擎中的游戏玩法逻辑。它的核心组成部分包括 Gameplay Ability&#xff08;定义和执行能力&#xff09;、Gameplay Effect&#xff08;应用和管理…...

Excel:vba实现合并工作表(表头相同)

这个代码应该也适用于一些表头相同的工作表的汇总&#xff0c;只需要修改想要遍历的表&#xff0c;适用于处理大量表头相同的表的合并 这里的汇总合并表 total 是我事先创建的&#xff0c;我觉得比用vba代码创建要容易一下&#xff0c;如果不事先创建汇总表就用下面的代码&…...

Redis:分布式 - 主从复制

Redis&#xff1a;分布式 - 主从复制 概念配置主从模式info replicationslave-read-onlytcp-nodelay 命令slaveof 主从结构一主一从一主多从 主从复制流程数据同步命令全量同步部分同步实时同步 节点晋升 概念 Redis的最佳应用&#xff0c;还是要在分布式系统中。对于非分布式…...

el-date-picker设置只有某些日期可选

示例图&#xff1a; <el-date-pickerv-model"topFormObj.upTime"type"date"value-format"timestamp"format"dd/MM/yyyy":picker-options"pickerOptions" /> 固定限制每周的周末周三不可选 data() {return {pickerOp…...

java数据库操作-cnblog

创建lib目录&#xff0c;填入jar包 选择 libraries添加lib目录 package nb;import java.sql.Connection; import java.sql.DriverManager; import java.sql.SQLException;public class JDBCtest {private static final String url "jdbc:mysql://localhost:3306/test?c…...

HCIP-HarmonyOS Application Developer 习题(九)

(多选) 1、HarmonyOS多窗口交互能力提供了以下哪几种交互方式&#xff1f; A. 全局消息通知 B.平行视界 C.悬浮窗 D.分屏 答案&#xff1a;BCD 分析&#xff1a;系统提供了悬浮窗、分屏、平行视界三种多窗口交互&#xff0c;为用户在大屏幕设备上的多任务并行、便捷的临时任务…...

redis集成到spring boot中使用

&#xff08;一&#xff09;添加依赖 redis服务器在官网中公开了自己使用的协议--RESP&#xff0c;所以我们可以使用这个协议来访问redis服务器&#xff0c;但是如果我们要自己实现库&#xff0c;那肯定是非常麻烦的&#xff0c;所以我们可以使用网上的库&#xff0c;我们直接调…...

Spring Boot、Spring MVC和Spring有什么区别

人要长大&#xff0c;就要学会不断接受事件的变化 —— 24.10.14 spring是一个IOC容器&#xff0c;用来管理Bean&#xff0c;使用依赖注入实现控制反转&#xff0c;可以很方便的整合各种框架&#xff0c;提供AOP机制弥补OOP的代码重复问题、更方便将不同类不同方法中的共同处理…...

Flip动画

前言 最近在做复图标库功能时&#xff0c;感觉这个功能在使用上有些“生硬”。如随机删除一个图标&#xff0c;后面的元素在视觉上是“瞬间移动”过来补位的。想着做个小优化&#xff0c;简单加个动画效果吧。 看起来确实“花里胡哨”了&#xff0c;实现也很简单&#xff0c; …...

Java通过RAG构建专属知识问答机器人_超详细

RAG&#xff1a;融合检索与生成的文本精准生成技术 检索增强生成&#xff08;RAG&#xff09;是一种技术&#xff0c;它通过结合检索模型和生成模型来提高文本生成的准确性。具体来说&#xff0c;RAG首先利用检索模型从私有或专有的数据源中搜索相关信息&#xff0c;然后将这些…...

2.1 使用点对点信道的数据链路层

欢迎大家订阅【计算机网络】学习专栏&#xff0c;开启你的计算机网络学习之旅&#xff01; 文章目录 前言1 通信信道类型2 数据链路3 帧4 透明传输5 差错检测 前言 在计算机网络通信中&#xff0c;数据链路层起着关键作用。它为直接相连的网络设备之间提供可靠的数据传输服务。…...

台式机来电自启动设置

在前司时&#xff0c;由于有些工作需要用到台式机&#xff0c;且一到节假日或者突然停电等情况&#xff0c;电脑每次都需要自己手动开机&#xff0c;后来研究了一下&#xff0c;发现可以在BIOS里面更改设置&#xff0c;从而变成关机的情况下&#xff0c;只要来电就能自动开机&a…...

【最新华为OD机试E卷-支持在线评测】考勤信息(100分)多语言题解-(Python/C/JavaScript/Java/Cpp)

🍭 大家好这里是春秋招笔试突围 ,一枚热爱算法的程序员 💻 ACM金牌🏅️团队 | 大厂实习经历 | 多年算法竞赛经历 ✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解 🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码 👏 感谢大家的订阅➕ 和 喜欢�…...

netdata保姆级面板介绍

netdata保姆级面板介绍 基本介绍部署流程下载安装指令选择设置KSM为什么要启用 KSM&#xff1f;如何启用 KSM&#xff1f;验证 KSM 是否启用注意事项 检查端口启动状态 netdata和grafana的区别NetdataGrafananetdata各指标介绍总览system overview栏仪表盘1. CPU2. Load3. Disk…...

苹果最新论文:LLM只是复杂的模式匹配 而不是真正的逻辑推理

大语言模型真的可以推理吗&#xff1f;LLM 都是“参数匹配大师”&#xff1f;苹果研究员质疑 LLM 推理能力&#xff0c;称其“不堪一击”&#xff01;苹果的研究员 Mehrdad Farajtabar 等人最近发表了一篇论文&#xff0c;对大型语言模型 &#xff08;LLM&#xff09; 的推理能…...

Python知识点:基于Python工具,如何使用Scikit-Image进行图像处理与分析

开篇&#xff0c;先说一个好消息&#xff0c;截止到2025年1月1日前&#xff0c;翻到文末找到我&#xff0c;赠送定制版的开题报告和任务书&#xff0c;先到先得&#xff01;过期不候&#xff01; 基于Python的Scikit-Image图像处理与分析指南 在Python的科学计算生态系统中&am…...

MongoDB初学者入门教学:与MySQL的对比理解

&#x1f3dd;️ 博主介绍 大家好&#xff0c;我是一个搬砖的农民工&#xff0c;很高兴认识大家 &#x1f60a; ~ &#x1f468;‍&#x1f393; 个人介绍&#xff1a;本人是一名后端Java开发工程师&#xff0c;坐标北京 ~ &#x1f389; 感谢关注 &#x1f4d6; 一起学习 &…...

Oracle AI Vector Search

Oracle AI Vector Search 是 Oracle Database 23ai 中引入的一项新技术&#xff0c;它允许用户在数据库中直接存储和高效查询向量数据。这项技术旨在简化应用程序的开发&#xff0c;并且支持不同维度和格式的向量。以下是 Oracle AI Vector Search 的一些关键特性和优势&#x…...

基于SpringBoot的健身会员管理系统实战分享

在这个充满活力的时代&#xff0c;我们自豪地呈现一款专为健身爱好者和专业人士设计的会员管理系统——一个集创新、效率与便捷于一体的解决方案。我们的系统基于强大的RuoYi-Vue框架构建&#xff0c;采用最新的Spring Boot和Vue3技术&#xff0c;确保了系统的高性能和用户友好…...

Git提交时Personal Access Token权限不足:如何正确配置workflow scope

1. 为什么Git提交会提示Personal Access Token权限不足&#xff1f; 最近在团队协作中遇到一个典型问题&#xff1a;当开发者尝试推送包含.github/workflows目录的代码到GitHub仓库时&#xff0c;系统突然报错refusing to allow a Personal Access Token to create or update w…...

BERT-base-uncased完全指南:从基础原理到实战应用

BERT-base-uncased完全指南&#xff1a;从基础原理到实战应用 【免费下载链接】bert-base-uncased 项目地址: https://ai.gitcode.com/hf_mirrors/ai-gitcode/bert-base-uncased 一、认知铺垫&#xff1a;为什么BERT改变了NLP格局&#xff1f; 1.1 BERT的突破性意义何…...

Qwen3-ASR-1.7B保姆级教程:解决‘识别结果不准确’的5类高频问题

Qwen3-ASR-1.7B保姆级教程&#xff1a;解决‘识别结果不准确’的5类高频问题 1. 引言&#xff1a;为什么你的语音识别总是不准&#xff1f; 你是不是遇到过这样的情况&#xff1a;用语音识别软件录音&#xff0c;结果出来的文字乱七八糟&#xff0c;完全不是你说的内容&#…...

SEO_移动端SEO优化的关键步骤与注意事项介绍

<h1 id"seo">移动端SEO优化的关键步骤与注意事项介绍</h1> <p>在互联网时代&#xff0c;移动端已经成为用户访问网站的主要途径。因此&#xff0c;移动端SEO优化变得尤为重要。本文将详细介绍移动端SEO优化的关键步骤与注意事项&#xff0c;帮助你…...

阿里云域名动态解析避坑指南:从AccessKey到API调用的完整流程

阿里云域名动态解析实战手册&#xff1a;从权限配置到高可用方案设计 对于拥有个人博客、家庭NAS或远程开发环境的技术爱好者而言&#xff0c;动态公网IP始终是个令人头疼的问题。每当ISP重新分配IP地址时&#xff0c;原本稳定的服务连接就会突然中断。本文将分享如何利用阿里云…...

从零到一:在本地CentOS环境完整部署yshop-drink扫码点餐系统的实战指南

1. 环境准备&#xff1a;从零搭建CentOS基础系统 第一次在本地部署yshop-drink扫码点餐系统时&#xff0c;我选择了CentOS 7.9作为基础环境。这个版本既稳定又兼容大多数现代软件包&#xff0c;特别适合作为生产环境使用。建议直接使用阿里云镜像站下载Minimal版本ISO文件&…...

ESP32 IDF环境下DHT11温湿度读取避坑指南:从时序图到数据拼接的完整解析

ESP32 IDF环境下DHT11温湿度读取避坑指南&#xff1a;从时序图到数据拼接的完整解析 在物联网设备开发中&#xff0c;温湿度传感器是最基础也最常用的环境感知元件之一。DHT11作为一款低成本、单总线数字输出的温湿度传感器&#xff0c;被广泛应用于各类嵌入式项目中。然而&…...

树莓派4b(armv8) 64位系统源码编译onnx实战指南

1. 环境准备&#xff1a;从零搭建树莓派4B开发环境 在树莓派4B上编译ONNX源码之前&#xff0c;我们需要先确保系统环境配置正确。我用的是一台4GB内存版本的树莓派4B&#xff0c;系统是最新的Raspberry Pi OS 64位版本。这里有个小细节要注意&#xff1a;很多教程还在用32位系统…...

高防服务器怎么选?360CDN 高防性价比分析

作为运维中小站点3年的老站长&#xff0c;前阵子被DDoS攻击搞得焦头烂额&#xff0c;网站频繁卡顿、宕机&#xff0c;损失不少流量。试过普通服务器加防护插件&#xff0c;基本形同虚设&#xff0c;后来陆续测试了360CDN高防以及其他几款主流高防产品&#xff0c;全程实测不吹不…...

LiuJuan20260223Zimage v1.0作品集:当传统工笔画遇见AI生成

LiuJuan20260223Zimage v1.0作品集&#xff1a;当传统工笔画遇见AI生成 1. 引言&#xff1a;一次跨越时空的艺术对话 想象一下&#xff0c;你拍了一张现代都市的夜景&#xff0c;或者设计了一张充满未来感的数字海报&#xff0c;然后&#xff0c;你把它交给一位深谙宋元笔法的…...