【力扣每日一题】2023.9.21 收集树中金币
目录
题目:
示例:
分析:
代码:
题目:
示例:
分析:
题目给我们一棵树,不过这棵树不是普通的树,而是无向无根树。给我们一个二维数组表示节点之间的连接关系,以及一个一维数组表示每个节点是否有金币。
我们可以从任何一个节点出发,并且可以收集距离两格的节点的金币,每次可以移动到相邻的节点。问我们要收集完所有的金币并且最终要回到起点,最少需要移动几次。
首先,题目说了这是一棵树,所以是不存在环的,两个节点之间连通的路径只会有唯一的一条。
因此我们不管选择哪一个节点当起点,都是可以到达任意一个节点的。
我们需要获取所有的金币,那么如果一个节点没有金币,并且这个节点是叶子节点,那么我们是不是可以将这个节点直接从树中移除,因为我们根本不需要走到这个节点。
我们把能删除的节点都删除了,是不是就说明剩下的节点都是我们需要走到或是收集金币的节点。
如果我们把整棵树剪到只剩下我们必须要走到的节点之后,答案就剩下节点数-1再乘2了。
为什么呢?
题目要求我们必须在收集完金币之后再返回原点,我们有n个必须到达的节点,由于这是树,是没有环的,因此节点之间的连线一共是n-1条。一来一回每个线段要走两次,所以答案是(n-1)*2
问题就变成了我们怎么把树的节点剪到只剩下我们必须要走的节点。
首先,没有金币的叶子节点我们是可以先删除的。判断依据也简单,如果一个节点没有金币,并且和这个节点连接的其他节点只有一个,那么它就是没有金币的叶子节点,可以把它删除。并且删除某个节点之后可能会诞生出新的无金币叶子节点,因此我们删除节点之后还需要判断一下与这个节点连接的节点是否也是无金币叶子节点,也就是延伸性地删除节点。
那么怎么删除呢,我们可没有构建出树来。
我们其实不需要真的删除。我们之前分析过了,答案就是剪枝后的节点数减1再乘2。我们可以当成一开始的树就是我们剪枝后的树,把答案初始化成总的节点数减1再乘2。每次我们删除一个节点就等于是移除了一个线段,把答案减2即可,这样就当成是删除一个节点了。
初步移除了没有金币的叶子节点之后剩下的节点就是我们要达到的节点或者是要收集金币的节点了。
我们把剩下的树看成是图,那么图边缘一圈的节点一定都是有金币的。
我们收集金币的时候可以距离金币节点两格,因此我们可以再一次把图的外围两层节点删除,不过删除是有条件的,最外层的叶子节点可以直接删除,不过第二层的节点我们得判断删除了外层节点后,第二层的节点是不是叶子节点,如果是我们才可以删除。
最终我们每次删除节点之后,都将答案-2,最终就是要返回出去的答案了。
不过最后还有一个问题,那就是如果整个树都是可以移除的,那么根据我们刚才说的每删除一个节点就把答案-2,而我们答案初始化是总的节点数减1再乘2,这样答案就变成了-2,因此最后我们做个判断,如果答案小于0,我们就返回0,反之就正常返回求出的答案。
代码:
class Solution {
public:unordered_map<int,vector<int>>pic; //记录节点连接图unordered_map<int,int>rel; //记录每个节点的邻接数量关系int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {int n=coins.size();int res=2*(n-1); //答案初始化成图中线段数乘2,表示每个线段都要走两边//建图for(auto& edge:edges){if(pic.find(edge[0])==pic.end()) pic[edge[0]]=vector<int>(0);if(pic.find(edge[1])==pic.end()) pic[edge[1]]=vector<int>(0);pic[edge[0]].push_back(edge[1]);pic[edge[1]].push_back(edge[0]);rel[edge[0]]++;rel[edge[1]]++;}queue<int> q;//删除无金币的叶子节点(可延伸)for(int i=0;i<n;i++){if(coins[i]==0 && rel[i]==1) q.push(i);}while(!q.empty()){res-=2; //减少一个线段,答案减2,因为默认每个线段走两次.int cur=q.front();q.pop();for(int i:pic[cur]){if(--rel[i]==1&&coins[i]==0) q.push(i);}}//确定到有金币的叶子节点的范围.for(int i=0;i<n;i++){if(coins[i]==1&&rel[i]==1) q.push(i);}res-=2*q.size();//减少叶子节点,不延伸(因为可以收集距离两格的金币,所以可以在边缘处再缩小一圈)while(!q.empty()){int x=q.front();q.pop();for(int j:pic[x]){if(--rel[j]==1) res-=2;}}if(res>0) return res;return 0;}
};
相关文章:

【力扣每日一题】2023.9.21 收集树中金币
目录 题目: 示例: 分析: 代码: 题目: 示例: 分析: 题目给我们一棵树,不过这棵树不是普通的树,而是无向无根树。给我们一个二维数组表示节点之间的连接关系ÿ…...

Python与数据分析--每天绘制Matplotlib库实例图片3张-第1天
目录 1.实例1--Bar color demo 2.实例2--Bar Label Demo 3.实例3--Grouped bar chart with labels 1.实例1--Bar color demo import matplotlib.pyplot as plt # 支持中文 plt.rcParams[font.sans-serif] [SimHei] # 用来正常显示中文标签 plt.rcParams[axes.unicode_minus…...

pycharm 中package, directory, sources root, resources root的区别
【遇到的问题】 导入yolov5中有utils文件,自己的代码中也有utils文件,使得yolov5中的这部分引用出错了。 【解决方案】 单独建立detection文件夹,把检测相关的都放在这里,yolov5是github上拉取的源码,发现yolov5中fr…...

【谢希尔 计算机网络】第2章 物理层
目录 通信基础 基本概念 两个公式lim 奈氏准则 香农定理 奈氏准则 VS 香农定理 编码与调制 编辑 物理层下面的传输媒体 导引型传输媒体 1. 双绞线 2. 同轴电缆 3. 光缆 非导引型传输媒体 无线电微波通信 卫星通信 无线局域网使用的 ISM 频段 信道复用技术 …...
Eclipse工具使用技巧
1、常用快捷键 ctrlshifto 快速导包 CtrlSpace 内容助理 说明:内容助理。提供对方法,变量,参数,javadoc等得提示,应运在多种场合,总之需要提示的时候可先按此快捷键。注:避免输入法的切换设置与此设置冲突 CtrlShiftSpace 变量提示 Ctrl/ 添加/消除//注释 CtrlShift/ 添加…...
python LeetCode 刷题记录 94
题目 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 代码 递归 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.righ…...

滴滴可观测平台 Metrics 指标实时计算如何实现了又准又省?
在滴滴,可观测平台的 Metrics 数据有一些实时计算的需求,承载这些实时计算需求的是一套又一套的 Flink 任务。之所以会有多套 Flink 任务,是因为每个服务按照其业务观测需要不同的指标计算,也就对应了不同数据处理拓扑。我们尽力抽…...

每天几道Java面试题:IO流(第五天)
目录 第五幕 、第一场)街边 友情提醒 背面试题很枯燥,加入一些戏剧场景故事人物来加深记忆。PS:点击文章目录可直接跳转到文章指定位置。 第五幕 、 第一场)街边 【衣衫褴褛老者,保洁阿姨,面试者老王】 衣衫褴褛老…...
js/axios/umi-request 根据后端返回的二进制流下载文件
type ResponseType {data: Blob;headers: {content-disposition?: string;}; }; // 下载 (创建a标签) export const downloadBlob (response: ResponseType) > {const blob response.data; // 获取响应中的 Blob 数据const contentDisposition response.headers[conten…...
软件评测师之流水线
目录 一.概念二.周期三.执行时间的计算 一.概念 程序在执行时多条指令可以层叠并行的技术。 二.周期 取指→分析→执行 指令执行的各个阶段里面,执行时间最长的为流水线的周期。 三.执行时间的计算 n条指令执行的总时间流水线计算公式:单条指令所需…...

Linux系统编程——网络编程的学习
Linux系统编程学习相关博文 Linux系统编程——文件编程的学习Linux系统编程——进程的学习Linux系统编程——进程间通信的学习Linux系统编程——线程的学习 Linux系统编程——网络编程的学习 一、概述1. TCP/UDP2. 端口号3. 字节序4. Sockt服务器和客户端的开发步骤1. 服务器2…...
Vue中的ref 和$refs的使用
ref 和$refs 作用:利用ref 和$refs可以用于获取dom元素,或组件实例 特点:查找范围→当前组件内(更精确稳定,原生的dom在vue子组件中查找最终也会扫描到父组件) 1. 获取dom 目标标签–添加ref 属性 <…...
Hive【非交互式使用、三种参数配置方式】
前言 今天开始学习 Hive,因为毕竟但凡做个项目基本就避不开用 Hive ,争取这学期结束前做个小点的项目。 第一篇博客内容还是比较少的,环境的搭建配置太琐碎没有写。 Hive 常用使用技巧 交互式使用 就是我们正常的进入 hive 命令行下的使用…...
基于Yolov8的工业小目标缺陷检测(1)
目录 1.工业油污数据集介绍 1.1 小目标定义 1.2 难点 1.3 工业缺陷检测算法介绍 1.3.1 YOLOv8...
Python文件操作和管理指南:打开、读取、写入和管理文件
文章目录 文件(File)打开文件使用 with ... as 语句打开文件读取文件内容读取大文件的方式逐行读取和读取全部行写文件操作文件定位seek()tell() 关闭文件 文件管理获取目录结构获取当前目录切换当前所在目录创建目录删除目录删除文件重命名文件 总结pyt…...

WebGL 用鼠标控制物体旋转
目录 鼠标控制物体旋转 如何实现物体旋转 示例程序(RotateObject.js) 代码详解 示例效果 鼠标控制物体旋转 有时候,WebGL程序需要让用户通过鼠标操作三维物体。这一节来分析示例程序RotateObject,该程序允许用户通过拖动&…...

Spring Boot魔法:简化Java应用的开发与部署
文章目录 什么是Spring Boot?1. 自动配置(Auto-Configuration)2. 独立运行(Standalone)3. 生产就绪(Production Ready)4. 大量的起步依赖(Starter Dependencies) Spring …...
参议院算法Java
Dota2 的世界里有两个阵营: Radiant(天辉)和 Dire(夜魇) Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定,他们以一个基于轮为过程的投票进行。在每一轮中,每一位参议员都可以行使两项权利中的一项: 禁止一名参议员的权利:参…...

前端提交规范 ESLint + Prettier + husky + lint-staged
如何统一代码风格,规范提交呢? 推荐使用前端规范全家桶 ESLint Prettier husky lint-staged。 eslint (github.com/eslint/esli…)JavaScript 代码检测工具,检测并提示错误或警告信息prettier (github.com/prettier/pr…) 代码自动化格式…...

python实现命令tree的效果
把所有的文档都传到了git上,但是内容过多找起来不方便,突发奇想如果能在readme中,递归列出所有文件同时添加上对应的地址,这样只需要搜索到对应的文件点击就能跳转过去了… 列出文件总得有个显示格式,所以就按照tree的来了… 用python实现命令tree的效果 首先,这是tree的效果…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...

20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...

【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
HTML中各种标签的作用
一、HTML文件主要标签结构及说明 1. <!DOCTYPE html> 作用:声明文档类型,告知浏览器这是 HTML5 文档。 必须:是。 2. <html lang“zh”>. </html> 作用:包裹整个网页内容,lang"z…...