2049. 统计最高分的节点数目
2049. 统计最高分的节点数目
- 题目
- 算法设计:深度优先搜索
题目
传送门:https://leetcode.cn/problems/count-nodes-with-the-highest-score/

算法设计:深度优先搜索
这题的核心是计算分数。
一个节点的分数 = 左子树节点数 × 右子树节点数 × 除自己外其他节点数。如下图:

删除某个节点之后,最多会把二叉树分割成 三个部分 :左子树、右子树、父节点及父节点的另一半子树(除自己外其他节点个数)。
使用 DFS 算出左子树节点数、右子树节点数。
因为知道树节点的总数,再计算除自己外其他节点个数。
- 除自己外其他节点个数 = 总数 - 1 - 左子树节点数 - 右子树节点数。
具体怎么解呢?
一个节点的分数 = 左子树节点数 × 右子树节点数 × 除自己外其他节点数
-
一是,需要清晰左子树节点数、右子树节点数,再通过总数 - 左右子树数 - 1,得到除自己外其他节点数
-
二是,三个数量都有了之后,相乘就是删除这个节点之后的分数,当然,这里有可能三个部分中缺失一部分或者两部分,缺失的部分用 1 来代替去相乘。
-
最终表达式:一个节点的分数 = 左子树节点数 × 右子树节点数 × (总数 - 左右子树数 - 1)
int dfs(vector<vector<int>> &tree, vector<long> &s, int i) { long score = 1, sum = 1; // 分数,节点总数,设置为long防止溢出for (int j : tree[i]) { // 遍历i所有子节点int cnt = dfs(tree, s, j); // 得出子树节点个数score *= cnt, sum += cnt; // 计算左右子树的得分,同时计算节点总数,累计每个子树节点数量和。因为分数等于三块的乘积,可同时计算节点数量、分数} s[i] = score * (max(1ll, (long)tree.size() - sum)); // 一个节点分数 = 左子树节点数 × 右子树节点数 × (总数 - 左右子树数 - 1)。1ll是把1改成long long类型return i != 0 ? sum : count(begin(s), end(s), *max_element(begin(s), end(s))); // *max_element查询最大分数,count统计最大分数的个数
}
int countHighestScoreNodes(vector<int>& parents) { // 题目给的 parents 数组不是树,先建树int n = parents.size();vector<vector<int>> tree(n); // 用数组存储树vector<long> s(n); for (int i = 1; i < n; ++i) tree[parents[i]].push_back(i); // 根据parents建树,tree[i]存储i的子节点return dfs(tree, s, 0); // 在图上dfs计算分数
}
相关文章:
2049. 统计最高分的节点数目
2049. 统计最高分的节点数目题目算法设计:深度优先搜索题目 传送门:https://leetcode.cn/problems/count-nodes-with-the-highest-score/ 算法设计:深度优先搜索 这题的核心是计算分数。 一个节点的分数 左子树节点数 右子树节点数 除自…...
Docker 架构简介
Docker 架构 Docker 包括三个基本概念: 镜像(Image):Docker 镜像(Image),就相当于是一个 root 文件系统。比如官方镜像 ubuntu:16.04 就包含了完整的一套 Ubuntu16.04 最小系统的 root 文件系统。容器&am…...
玄子Share-BCSP助学手册-JAVA开发
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-b2gPyAnt-1676810001349)(./assets/%E7%8E%84%E5%AD%90Share%E4%B8%89%E7%89%88.jpg)] 玄子Share-BCSP助学手册-JAVA开发 前言: 此文为玄子,复习BCSP一二期后整理的文章&#x…...
利用React实现多个场景下的鼠标跟随框提示框
前言 鼠标跟随框的作用如下图所示,可以在前端页面上,为我们后续的鼠标操作进行提示说明,提升用户的体验。本文将通过多种方式去实现,从而满足不同场景下的需求。 实现原理 实现鼠标跟随框的原理很简单,就是监听鼠标在…...
【安全知识】——如何绕过cdn获取真实ip
作者名:白昼安全主页面链接: 主页传送门创作初心: 以后赚大钱座右铭: 不要让时代的悲哀成为你的悲哀专研方向: web安全,后渗透技术每日鸡汤: 现在的样子是你想要的吗?cdn简单来说就是…...
JavaScript内存泄露和垃圾回收机制
1、是什么?内存泄露(Memory leak)是在计算机科学中,由于疏忽或错误造成程序未能释放已经不再使用的内存。并非指内存在物理上的消失,而是应用程序分配某段内存后,由于设计错误,导致在释放该段内…...
Kubernetes02:知识图谱
Kubernetes01:知识图谱 MESOS APACHE 分布式资源管理框架 2019-5 Twitter 》 Kubernetes Docker Swarm 2019-07 阿里云宣布 Docker Swarm 剔除 Kubernetes Google 10年容器化基础架构 borg Go语言 Borg 特点 轻量级:消耗资源小 开源 弹性伸缩 负载均…...
nginx-服务器banner泄漏风险
http { server_tokens off; # 隐藏Nginx版本号 .... }...
GCC 同名符号冲突解决办法
一、绪论 作为 C/C 的开发者,大多数都会清楚课本上动态库以及静态库的优缺点,在教科书上谈及到动态库的一个优点是可以节约磁盘和内存的空间,多个可执行程序通过动态库加载的方式共用一段代码段 ;而时至今日,再看看上…...
下一代视频编码技术2023
下一代视频编码技术 下面将从这两个角度来介绍华为云视频在下一代视频编码技术上的一些工作。这些技术得益于华为2012 媒体技术院全力支持。 2.1 下一代视频编码标准技术 从上图可以看出,下一代的视频编码标准大概分为三个阵营或者三个类型: 国际标准…...
最新最全中小微企业研究数据:海量创业公司信息与获取投资信息(1985-2021年)
一、企业获取投资名单&资方信息 数据来源:搜企网、企查查、天眼查 时间跨度:1985年8月-2021年9月 区域范围:全国范围 数据字段:企业名称、时间、获得投资金额以及投资方信息 部分数据: DateCompany_nameUnit…...
springboot数据源浅析
DataSourceAutoConfiguration分析 SpringBoot有一个自动配置DataSourceAutoConfiguration 为数据源配置 /META-INF/spring.factories文件找到DataSourceAutoConfiguration配置类 一、先来看下DataSourceAutoConfiguration配置类生效的时机,观察源码发现 Configura…...
2022黑马Redis跟学笔记.实战篇(七)
2022黑马Redis跟学笔记.实战篇 七4.11.附近的店铺功能4.11.1. GEO数据结构的基本用法1. 附近商户-导入店铺数据到GEO4.11.2. 获取附近的店铺1. 附近商户-实现附近商户功能4.9. 签到功能4.9.1.BitMap原理1. 用户签到-BitMap功能演示4.9.2.实现签到功能4.9.3.实现补签功能4.9.4.统…...
QT mp3音乐播放器实现框架,Qt鼠标事件,网络编程,QSqlite,Json解析,HTTP请求等
QT mp3音乐播放器实现框架,Qt鼠标事件,网络编程,QSqlite,Json解析,HTTP请求等框架搭建UI设计mp3.hmp3.cpp隐藏窗口标题 最大化 最小化 关闭框架搭建 .pro添加 # 网络 添加多媒体 数据库 QT network multimedia sql添加头…...
硬件学习 软件Cadence day04 PCB 封装绘制
1.文章内容: 1. 贴片式电容 PCB 封装绘制 (型号 c0603 ) 2. 贴片式电阻 PCB 封装绘制 (型号 r0603 ) 3. 安规式电容 PCB 封装绘制 (这个就是 有一个电容,插入一个搞好的孔里面 …...
【Java】yield()和join()区别
一、java 线程调度的背景 java虚拟机要求在多线程中实现 preemptive和priority-based调度,这意味着java中每一个线程被分配了特定的优先级,正整数在定义好的范围内不断减。优先级可以通过开发者改变但是java虚拟机从不改变线程的优先级,即使…...
【MySQL】Java连接MySQL数据库(封装版只需会MySQL)
一、准备普通项目如果创建的是普通的Java项目,我们需要去maven仓库下载jdbc驱动包然导入项目中就能使用,具体步骤详见MySQL数据库之Java中如何使用数据库【JDBC编程】maven项目如果创建的项目是maven项目,我们只需在pom.xml文件里引入一组依赖…...
【java基础】运算符
运算符 operator 运算符优先级 Operators 操作员Precedence 优先级postfix 后缀expr expr--unary 一元的expr --expr expr -expr ~ !multiplicative 〔数〕乘法的 / %additive 添加剂 -shift 移动<< >> >>>relational 关系的< > < > insta…...
带噪学习-概述
在实际应用的时候,我们的样本不会是完全干净的,即存在噪声样本。那使用存在噪声的样本时,我们如何更有效的进行模型学习呢?Label Dependent Nose样本选择(Sample Selection)第一种很直接的想法,…...
Scratch少儿编程案例-多彩打地鼠
专栏分享 点击跳转=>Unity3D特效百例点击跳转=>案例项目实战源码点击跳转=>游戏脚本-辅助自动化点击跳转=>Android控件全解手册点击跳转=>Scratch编程案例👉关于作者...
DedeCMS文件包含漏洞深度剖析:为什么一个‘无害’的txt文件能让你getshell?
DedeCMS文件包含漏洞技术解析:从文本文件到系统沦陷的连锁反应 在内容管理系统(CMS)的安全领域,最危险的漏洞往往藏匿于最平凡的功能之中。DedeCMS作为国内广泛使用的开源CMS,其文件包含漏洞(CVE-2023-2928…...
解放词库自由:跨平台词库迁移的全场景解决方案
解放词库自由:跨平台词库迁移的全场景解决方案 【免费下载链接】imewlconverter ”深蓝词库转换“ 一款开源免费的输入法词库转换程序 项目地址: https://gitcode.com/gh_mirrors/im/imewlconverter 当你更换新手机时,是否曾为输入法里积累多年的…...
Leather Dress Collection 实战:为开源项目自动生成 README 与贡献指南
Leather Dress Collection 实战:为开源项目自动生成 README 与贡献指南 你有没有过这样的经历?辛辛苦苦写好了一个开源项目,代码功能强大,架构清晰,但一想到要写 README、贡献指南、行为准则这些文档,头就…...
FireRedASR Pro代码详解:从音频预处理到文本后处理全流程
FireRedASR Pro代码详解:从音频预处理到文本后处理全流程 1. 引言 如果你对语音识别感兴趣,想知道一段音频是怎么变成文字的,那么这篇文章就是为你准备的。我们这次不聊怎么用现成的工具,而是直接打开一个叫FireRedASR Pro的语音…...
16G内存就够了!GPT-OSS-20B量化版实测,响应速度快人一步
16G内存就够了!GPT-OSS-20B量化版实测,响应速度快人一步 1. 开箱即用的高性能AI体验 在AI大模型遍地开花的今天,找到一个既强大又能在普通设备上流畅运行的模型实属不易。GPT-OSS-20B的出现打破了这一局面——这个由OpenAI开源的210亿参数模…...
告别官方版SSE2坑!用linsys_pjsip 2.11.8在ARM32平台快速集成SIP与WebRTC AEC3
ARM32平台高效集成SIP与WebRTC AEC3:linsys_pjsip 2.11.8实战指南 在嵌入式音视频通信领域,ARM32架构设备因其低功耗和成本优势被广泛应用。但当你尝试在这些设备上部署PJSIP时,官方版本的SSE2指令集依赖就像一堵高墙,让许多开发者…...
ddsad
sdsfdjsufhfsuh...
告别老系统!手把手教你用欧空局新版哥白尼数据空间下载Sentinel-2影像(附波段组合预览技巧)
告别老系统!手把手教你用欧空局新版哥白尼数据空间下载Sentinel-2影像(附波段组合预览技巧) 当欧空局宣布停用老版数据下载系统时,许多遥感从业者都感到一丝不安——毕竟旧系统虽然界面陈旧,但操作流程早已烂熟于心。作…...
谱聚类实战:如何让声纹模型自动分辨一段录音里有几个人说话?
谱聚类在声纹识别中的应用:如何自动判断录音中的说话人数量 想象一下,你手头有一段长达两小时的会议录音,里面有五位不同声线的参与者交替发言。作为开发者,你需要设计一个系统,不仅能识别每个人的声音特征,…...
【逆向实战】Unity3D+il2cpp手游反编译与逻辑修改全流程解析【IDA Pro+il2CppDumper】
1. 从零开始理解Unity3Dil2cpp逆向 第一次接触手游逆向的朋友可能会被"il2cpp"这个术语吓到。其实简单来说,il2cpp就是Unity3D用来提升游戏性能的编译方案——它把C#代码先转成C,再编译成原生机器码。这种架构虽然让游戏跑得更快,但…...
