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

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. 统计最高分的节点数目题目算法设计&#xff1a;深度优先搜索题目 传送门&#xff1a;https://leetcode.cn/problems/count-nodes-with-the-highest-score/ 算法设计&#xff1a;深度优先搜索 这题的核心是计算分数。 一个节点的分数 左子树节点数 右子树节点数 除自…...

Docker 架构简介

Docker 架构 Docker 包括三个基本概念: 镜像&#xff08;Image&#xff09;&#xff1a;Docker 镜像&#xff08;Image&#xff09;&#xff0c;就相当于是一个 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开发 前言&#xff1a; 此文为玄子&#xff0c;复习BCSP一二期后整理的文章&#x…...

利用React实现多个场景下的鼠标跟随框提示框

前言 鼠标跟随框的作用如下图所示&#xff0c;可以在前端页面上&#xff0c;为我们后续的鼠标操作进行提示说明&#xff0c;提升用户的体验。本文将通过多种方式去实现&#xff0c;从而满足不同场景下的需求。 实现原理 实现鼠标跟随框的原理很简单&#xff0c;就是监听鼠标在…...

【安全知识】——如何绕过cdn获取真实ip

作者名&#xff1a;白昼安全主页面链接&#xff1a; 主页传送门创作初心&#xff1a; 以后赚大钱座右铭&#xff1a; 不要让时代的悲哀成为你的悲哀专研方向&#xff1a; web安全&#xff0c;后渗透技术每日鸡汤&#xff1a; 现在的样子是你想要的吗&#xff1f;cdn简单来说就是…...

JavaScript内存泄露和垃圾回收机制

1、是什么&#xff1f;内存泄露&#xff08;Memory leak&#xff09;是在计算机科学中&#xff0c;由于疏忽或错误造成程序未能释放已经不再使用的内存。并非指内存在物理上的消失&#xff0c;而是应用程序分配某段内存后&#xff0c;由于设计错误&#xff0c;导致在释放该段内…...

Kubernetes02:知识图谱

Kubernetes01&#xff1a;知识图谱 MESOS APACHE 分布式资源管理框架 2019-5 Twitter 》 Kubernetes Docker Swarm 2019-07 阿里云宣布 Docker Swarm 剔除 Kubernetes Google 10年容器化基础架构 borg Go语言 Borg 特点 轻量级&#xff1a;消耗资源小 开源 弹性伸缩 负载均…...

nginx-服务器banner泄漏风险

http { server_tokens off; # 隐藏Nginx版本号 .... }...

GCC 同名符号冲突解决办法

一、绪论 作为 C/C 的开发者&#xff0c;大多数都会清楚课本上动态库以及静态库的优缺点&#xff0c;在教科书上谈及到动态库的一个优点是可以节约磁盘和内存的空间&#xff0c;多个可执行程序通过动态库加载的方式共用一段代码段 &#xff1b;而时至今日&#xff0c;再看看上…...

下一代视频编码技术2023

下一代视频编码技术 下面将从这两个角度来介绍华为云视频在下一代视频编码技术上的一些工作。这些技术得益于华为2012 媒体技术院全力支持。 2.1 下一代视频编码标准技术 从上图可以看出&#xff0c;下一代的视频编码标准大概分为三个阵营或者三个类型&#xff1a; 国际标准…...

最新最全中小微企业研究数据:海量创业公司信息与获取投资信息(1985-2021年)

一、企业获取投资名单&资方信息 数据来源&#xff1a;搜企网、企查查、天眼查 时间跨度&#xff1a;1985年8月-2021年9月 区域范围&#xff1a;全国范围 数据字段&#xff1a;企业名称、时间、获得投资金额以及投资方信息 部分数据&#xff1a; DateCompany_nameUnit…...

springboot数据源浅析

DataSourceAutoConfiguration分析 SpringBoot有一个自动配置DataSourceAutoConfiguration 为数据源配置 /META-INF/spring.factories文件找到DataSourceAutoConfiguration配置类 一、先来看下DataSourceAutoConfiguration配置类生效的时机&#xff0c;观察源码发现 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音乐播放器实现框架&#xff0c;Qt鼠标事件&#xff0c;网络编程&#xff0c;QSqlite,Json解析&#xff0c;HTTP请求等框架搭建UI设计mp3.hmp3.cpp隐藏窗口标题 最大化 最小化 关闭框架搭建 .pro添加 # 网络 添加多媒体 数据库 QT network multimedia sql添加头…...

硬件学习 软件Cadence day04 PCB 封装绘制

1.文章内容&#xff1a; 1. 贴片式电容 PCB 封装绘制 &#xff08;型号 c0603 &#xff09; 2. 贴片式电阻 PCB 封装绘制 &#xff08;型号 r0603 &#xff09; 3. 安规式电容 PCB 封装绘制 &#xff08;这个就是 有一个电容&#xff0c;插入一个搞好的孔里面 …...

【Java】yield()和join()区别

一、java 线程调度的背景 java虚拟机要求在多线程中实现 preemptive和priority-based调度&#xff0c;这意味着java中每一个线程被分配了特定的优先级&#xff0c;正整数在定义好的范围内不断减。优先级可以通过开发者改变但是java虚拟机从不改变线程的优先级&#xff0c;即使…...

【MySQL】Java连接MySQL数据库(封装版只需会MySQL)

一、准备普通项目如果创建的是普通的Java项目&#xff0c;我们需要去maven仓库下载jdbc驱动包然导入项目中就能使用&#xff0c;具体步骤详见MySQL数据库之Java中如何使用数据库【JDBC编程】maven项目如果创建的项目是maven项目&#xff0c;我们只需在pom.xml文件里引入一组依赖…...

【java基础】运算符

运算符 operator 运算符优先级 Operators 操作员Precedence 优先级postfix 后缀expr expr--unary 一元的expr --expr expr -expr ~ !multiplicative 〔数〕乘法的 / %additive 添加剂 -shift 移动<< >> >>>relational 关系的< > < > insta…...

带噪学习-概述

在实际应用的时候&#xff0c;我们的样本不会是完全干净的&#xff0c;即存在噪声样本。那使用存在噪声的样本时&#xff0c;我们如何更有效的进行模型学习呢&#xff1f;Label Dependent Nose样本选择&#xff08;Sample Selection&#xff09;第一种很直接的想法&#xff0c;…...

Scratch少儿编程案例-多彩打地鼠

专栏分享 点击跳转=>Unity3D特效百例点击跳转=>案例项目实战源码点击跳转=>游戏脚本-辅助自动化点击跳转=>Android控件全解手册点击跳转=>Scratch编程案例👉关于作者...

千问3.5-2B参数详解:max_new_tokens=192如何平衡响应长度与推理延迟?实测数据

千问3.5-2B参数详解&#xff1a;max_new_tokens192如何平衡响应长度与推理延迟&#xff1f;实测数据 1. 模型概述 千问3.5-2B是Qwen系列中的小型视觉语言模型&#xff0c;具备图片理解与文本生成双重能力。这个2B参数的轻量级模型特别适合需要快速响应的应用场景&#xff0c;…...

告别老系统!手把手教你用欧空局新版哥白尼数据空间下载Sentinel-2影像(附波段组合预览技巧)

告别老系统&#xff01;手把手教你用欧空局新版哥白尼数据空间下载Sentinel-2影像&#xff08;附波段组合预览技巧&#xff09; 当欧空局宣布停用老版数据下载系统时&#xff0c;许多遥感从业者都感到一丝不安——毕竟旧系统虽然界面陈旧&#xff0c;但操作流程早已烂熟于心。作…...

history 常见优化配置

文章目录 一、写在哪个文件生效?(关键) ✅ Bash 环境下生效位置(最常见) 1️⃣ 全局生效(所有用户) ✅ 推荐方式(最规范) 2️⃣ 全局兜底(老系统) 3️⃣ 当前用户生效 ✅ 各文件加载顺序(很重要) 二、不同场景推荐配置位置 三、验证是否生效 四、一句话总结(运维…...

力扣热门100题之合并区间

这题核心就两步&#xff1a;先按起点排序 → 再逐个合并重叠区间 思路 1. 按每个区间的左端点从小到大排序 2. 用一个列表保存结果 3. 遍历每个区间&#xff1a; ◦ 如果结果为空&#xff0c;直接加入 ◦ 否则看当前区间起点 ≤ 最后一个区间终点 → 重叠&#xff0c;合并 ◦ 不…...

嵌入式系统错误处理策略与实现技术

1. 嵌入式系统中的错误处理概述在嵌入式软件开发中&#xff0c;错误处理是确保系统稳定性和可靠性的关键环节。与通用计算机系统不同&#xff0c;嵌入式系统往往运行在资源受限的环境中&#xff0c;且需要长时间不间断工作&#xff0c;这使得错误处理策略的选择尤为重要。嵌入式…...

CEEMDAN-VMD-Transformer-GRU二次分解+编码器+门控循环单元多元时间序列预测

一、研究背景 实际工程与科学数据&#xff08;如振动信号、电力负荷、金融时序&#xff09;常呈现非线性、非平稳特征&#xff0c;单一预测模型难以充分提取多尺度信息。为此&#xff0c;结合自适应信号分解&#xff08;CEEMDAN、VMD&#xff09;与深度学习&#xff08;Transfo…...

【2026年最新600套毕设项目分享】springboot智能民宿预定与游玩系统(14340)

有需要的同学&#xff0c;源代码和配套文档领取&#xff0c;加文章最下方的名片哦 一、项目演示 项目演示视频 二、资料介绍 完整源代码&#xff08;前后端源代码SQL脚本&#xff09;配套文档&#xff08;LWPPT开题报告/任务书&#xff09;远程调试控屏包运行一键启动项目&…...

比话降AI和嘎嘎降AI处理80%+AI率哪个更好

比话降AI和嘎嘎降AI是目前市面上处理极高AI率最有效的两款工具&#xff0c;但很多人不知道该选哪个。 这篇文章做一个直接的对比&#xff1a;两款工具在AI率80%场景下&#xff0c;各有什么优势和劣势&#xff0c;你的情况适合哪个。 基础信息对比 项目比话降AI嘎嘎降AI官网b…...

Unity WebGL小游戏上抖音,从踩坑到上线:一份避坑指南与性能优化清单

Unity WebGL小游戏上抖音&#xff1a;性能优化与避坑实战手册 当你第一次将Unity WebGL小游戏发布到抖音平台时&#xff0c;可能会遇到各种意想不到的性能瓶颈和兼容性问题。iOS设备上的内存限制、WebGL与Native的性能差距、包体大小控制等挑战&#xff0c;都可能让原本流畅的游…...

从频谱仪读数到测试报告:深入理解dBμV/m、dBm这些单位在EMC辐射发射测试中的真实含义

从频谱仪读数到测试报告&#xff1a;深入理解dBμV/m、dBm这些单位在EMC辐射发射测试中的真实含义 在电磁兼容&#xff08;EMC&#xff09;测试实验室里&#xff0c;工程师们每天都要面对频谱分析仪上跳动的数字——那些以dBμV/m、dBm为单位的读数&#xff0c;直接决定着产品能…...