【力扣每日一题】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的效果…...
Deformable DETR(2020 ICLR)
Deformable DETR(2020 ICLR) detr训练epochs缩小十倍,小目标性能更好 Deformable attention 结合变形卷积的稀疏空间采样和Transformer的关系建模能力 使用多层级特征层特征,不需要使用FPN的设计(直接使用backbone多层级输出&a…...
springboot01
目录 新建Maven工程,什么都不选 pom.xml加上 新建包top.cjz.controller 新建类HelloController 新建类HelloApplication 运行浏览器访问 新建Maven工程,什么都不选 pom.xml加上 <!--springboot工程需要继承的父工程--> <parent…...
虚拟机中window/ubuntu系统如何联网?
以下内容源于网络资源的学习与整理,如有侵权请告知删除。 参考博客 (1)VMware虚拟机中Windows11无法连接网络 (2)图解vmware虚拟机win8无线上网 (3)VMware中VMnet0、VMnet1、VMnet8是什么 &…...
计算物理专题----随机游走实战
计算物理专题----随机游走实战 Problem 1 Implement the 3D random walk 拟合线 自旋的 拟合函数(没有数学意义) 参数:0.627,3.336,0.603,-3.234 自由程满足在一定范围内的均匀分布以标准自由程为单位长度,…...
《思维与智慧》简介及投稿邮箱
《思维与智慧》自1982年创刊,经国家新闻出版署批准,由河北省教育厅主管,河北行知文化传媒有限责任公司主办的益智励 志类大众文化期刊。 《思维与智慧》办刊宗旨是:“开发思维,启迪智慧,滋润心灵”&#x…...
flask+python快速搭建
app.py """APP 入口模块""" from traceback import format_excfrom api_limiter import limiter from flask import Flask, jsonify import loggingfrom controller import api_sql_blueapp Flask(__name__) limiter.init_app(app) app.regist…...
基于微信小程序的美术馆预约平台设计与实现(源码+lw+部署文档+讲解等)
前言 💗博主介绍:✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌💗 👇🏻…...
ruoyi-vue-pro yudao 项目商城 mall 模块启用及相关SQL脚本
目前ruoyi-vue-pro 项目虽然开源,但是商城 mall 模块被屏蔽了,查看文档却要收费 199元(知识星球),价格有点太高了吧。 分享下如何启用 mall 模块,顺便贴上sql相关脚本。 一、启用模块 修改根目录 pom.xm…...
default 和 delete 与默认构造函数 的使用
前言 使用default和delete关键字来干预编译器自动生成的函数。让我详细解释一下这些知识点: 正文 编译器生成的默认构造函数: 如果类A没有定义任何构造函数,那么编译器会自动生成一个无参的默认构造函数 A()。这个默认构造函数实际上是一个…...
【开发篇】一、热部署
文章目录 1、手工启动热部署2、自动启动热部署3、热部署范围配置4、关闭热部署功能 1、手工启动热部署 日常开发与调试,改几行代码想看效果就得手动点重启,很繁琐,接下来考虑启动热部署。首先引入springboot开发者工具: <dep…...
什么网站有项目做/开平网站设计
Mybatis一级缓存和二级缓存缓存到底是什么东西呢??缓存是数据交换的缓冲区,简单点理解就是存在于内存中的临时数据。那我们为什么要使用缓存?例如我们每次查询用户信息,每次都要请求数据库,数据库会编译并执行你的SQL…...
党的建设专题网站/360提交网站收录入口
javascript是面向过程的,只要请引用.js文件即可访问他的方法(function),并且传统方式会定义很多全局变量。如果大量使用javascript难免会出现变量覆盖,或function同名。 所以我们要将javascript封装成class,…...
手机网站建设方案/seo排名赚
T1:背单词(bzoj4567)题解代码 T2:幸运数字(bzoj4568)题解代码 T3:萌萌哒(bzoj4569)T4:妖怪(bzoj4570)T5:美味(bzoj4571)题解代码 T6:围棋(bzoj4572)总结 T1:背单词(bzoj4567) 题解 关键词:trie树 贪心 题意有些难懂,简单解释一下。 对于在位置xx的单…...
wordpress静态页没有标题/百度官网客服
数据类型、运算符与表达式C的数据类型注:数据类型决定:1. 数据占内存字节数2. 数据取值范围3. 可以进行的操作常量与变量一、常量和符号常量1.定义:程序运行过程中,其值不能被改变的量(常数)2.分类…...
wordpress插件在哪/中国网站建设公司
近年来,云计算技术成为兵家必争之地,已经成为数字经济时代的基础,金融科技则是各种产业的基础设施力。过去,我们谈到金融行业使用技术手段,尤其是互联网技术,往往是为了优化流程、改善效率,始终…...
夺目视频制作网站/做营销型网站的公司
.text_overflow{width:6.5rem;white-space:nowrap;text-overflow:ellipsis;-o-text-overflow:ellipsis;overflow:hidden; }...