当前位置: 首页 > 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编程案例👉关于作者...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

6.9本日总结

一、英语 复习默写list11list18&#xff0c;订正07年第3篇阅读 二、数学 学习线代第一讲&#xff0c;写15讲课后题 三、408 学习计组第二章&#xff0c;写计组习题 四、总结 明天结束线代第一章和计组第二章 五、明日计划 英语&#xff1a;复习l默写sit12list17&#…...

关于 ffmpeg设置摄像头报错“Could not set video options” 的解决方法

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/148515355 长沙红胖子Qt&#xff08;长沙创微智科&#xff09;博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV…...

Xcode 16.2 版本 pod init 报错

Xcode 版本升级到 16.2 后&#xff0c;项目执行 pod init 报错&#xff1b; ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchron…...

四、Sqoop 导入表数据子集

作者&#xff1a;IvanCodes 日期&#xff1a;2025年6月4日 专栏&#xff1a;Sqoop教程 当不需要将关系型数据库中的整个表一次性导入&#xff0c;而是只需要表中的一部分数据时&#xff0c;Sqoop 提供了多种方式来实现数据子集的导入。这通常通过过滤条件或选择特定列来完成。 …...

【Unity】R3 CSharp 响应式编程 - 使用篇(二)

一、通用的事件监听用法 using System;using R3;using UnityEngine;namespace Aladdin.Standard.Observable.Common{public class CommonObservable : MonoBehaviour{// 默认会调用1次public SerializableReactiveProperty<int> serializableReactiveProperty;…...

MySQL-运维篇

运维篇 日志 错误日志 错误日志是 MySQL 中最重要的日志之一&#xff0c;它记录了当 mysqld 启动和停止时&#xff0c;以及服务器在运行过程中发生任何严重错误时的相关信息当数据库出现任何故障导致无法正常使用时&#xff0c;建议首先查看此日志。 该日志是默认开启的&am…...