【力扣每日一题】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;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/138434.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Open3D 进阶(11)使用GMM-Tree算法对点云配准

GMM-Tree算法 一、算法原理1、主要函数2、参考文献二、代码实现三、结果展示1、点云初始位置2、配准后的位置四、测试数据本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫。 一、算法原理 1、

快速用Python进行数据分析技巧详解

概要 一些小提示和小技巧可能是非常有用的&#xff0c;特别是在编程领域。有时候使用一点点黑客技术&#xff0c;既可以节省时间&#xff0c;还可能挽救“生命”。 一个小小的快捷方式或附加组件有时真是天赐之物&#xff0c;并且可以成为真正的生产力助推器。所以&#xff0…

解密list的底层奥秘

&#x1f388;个人主页:&#x1f388; :✨✨✨初阶牛✨✨✨ &#x1f43b;强烈推荐优质专栏: &#x1f354;&#x1f35f;&#x1f32f;C的世界(持续更新中) &#x1f43b;推荐专栏1: &#x1f354;&#x1f35f;&#x1f32f;C语言初阶 &#x1f43b;推荐专栏2: &#x1f354;…

Android之MediaMetricsService实现本质(四十二)

简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只有行动才是治疗恐惧和懒惰的唯一良药. 更多原创,欢迎关注:Android…

王江涛十天搞定考研词汇

学习目标&#xff1a; 考研词汇 学习内容&#xff1a; 2023-9-17 第一天考研词汇 学习时间&#xff1a; 开始:2023-9-17 结束:进行中 学习产出&#xff1a; 2023-9-17intellect智力&#xff1b;知识分子intellectual智力的&#xff1b;聪明的intellectualize使...理智化&a…

JsonUtils

1、工具类 package com.atguigu.utils;import com.fasterxml.jackson.annotation.JsonInclude; import com.fasterxml.jackson.core.JsonProcessingException; import com.fasterxml.jackson.core.type.TypeReference; import com.fasterxml.jackson.databind.Deserialization…

flink集群与资源@k8s源码分析-回顾

本章是分析系列最后一章,作为回顾,以运行架构图串联起所有分析场景 1 启动集群,部署集群(提交k8s),新建作业管理器组件 2 构建和启动flink master组件 3 提交作业,N/A

RocketMQ 消费者分类与分组

文章目录 消费者分类PushConsumerPushConsumer 内部原理使用注意事项 SimpleConsumerinvisibleDuration 消息不可见时间 消费者分组&#xff08;消费者负载均衡&#xff09;广播消费和共享消费负载均衡策略多个消费者消费顺序消息多消费者消费顺序消息示例 消费者分组管理关闭自…

IDEA最新激 20活23码

人狠话不多 大家好&#xff0c;最近Intelli Idea官方的校验规则进行了更新&#xff0c;之前已经成功激20活23的Idea可能突然无法使用了。 特地从网上整理了最新、最稳定的激20活23码分享给大家&#xff0c;希望可以帮助那些苦苦为寻找Idea激20活23码而劳累的朋友们。 本激23…

外国固定资产管理系统功能有哪些

很多公司都在寻找提高自己资产管理效益的方法。为了满足这一要求&#xff0c;国外的固定资产管理系统已经发展成多种形式。以下是国外一些常见的固定资产管理系统的特点:自动化和智能化:许多现代固定资产管理系统采用自动化和数字化技术&#xff0c;以简化流程&#xff0c;减少…

Windows本地mysql 的安装教程(一步一步进行安装)

目录 1 下载安装包2 安装 1 下载安装包 下载网址&#xff1a; https://dev.mysql.com/downloads/ 选择这个 2 安装 编写MySQL配置文件 在解压目录下新建my.ini文件 将下面文本拷贝进my,ini文件中 [mysqld] # 设置3306端口 port3306 # 设置mysql的安装目录 ----------…

18.备忘录模式(Memento)

意图&#xff1a;在不破坏封装性的前提下&#xff0c;捕获一个对象的内部状态&#xff0c;并在该对象之外保存这个状态&#xff0c;这样就可以在以后将该对象恢复到原先保存的状态。 上下文&#xff1a;某些对象的状态在转换过程中&#xff0c;可能由于某种需要&#xff0c;要求…

Qt重写QTreeWidget实现拖拽

介绍 此文章记录QTreeWidget的重写进度&#xff0c;暂时停滞使用&#xff0c;重写了QTreeWidget的拖拽功能&#xff0c;和绘制功能&#xff0c;自定义了数据结构&#xff0c;增加复制&#xff0c;粘贴&#xff0c;删除&#xff0c;准备实现动态刷新数据支持千万数据动态刷新&a…

Docker 容器数据卷

是什么 卷就是目录或文件&#xff0c;存在于一个或多个容器中&#xff0c;由docker挂载到容器&#xff0c;但不属于联合文件系统&#xff0c;因此能够绕过Union File System提供一些用于持续存储或共享数据的特性&#xff1a;卷的设计目的就是数据的持久化&#xff0c;完全独立…

[设计模式] 浅谈SOLID设计原则

目录 单一职责原则开闭原则里氏替换原则接口隔离原则依赖倒转原则 SOLID是一个缩写词&#xff0c;代表以下五种设计原则 单一职责原则 Single Responsibility Principle, SRP开闭原则 Open-Closed Principle, OCP里氏替换原则 Liskov Substitution Principle, LSP接口隔离原则 …

Linux 中的make/makefile

一&#xff1a;背景 make是一个命令工具&#xff0c;是一个解释makefifile中指令的命令工具&#xff0c;一般来说&#xff0c;大多数的IDE都有这个命令&#xff0c;比如&#xff1a;Delphi的make&#xff0c;Visual C的nmake&#xff0c;Linux下GNU的make。可见&#xff0c;mak…

【Xilinx】基于MPSoC的OpenAMP实现(一)

【Xilinx】基于MPSoC的OpenAMP实现&#xff08;一&#xff09; 一、开发环境1、开发思路2、下载官方bsp包 二、编译Linux1、配置petalinux环境变量2、创建工程3、进入目录4、设置缓存目录&#xff08;重点&#xff1a;可离线编译&#xff0c;加快编译速度&#xff09;5、配置u-…

JMeter断言之JSON断言

JSON断言 若服务器返回的Response Body为JSON格式的数据&#xff0c;使用JSON断言来判断测试结果是较好的选择。 首先需要根据JSON Path从返回的JSON数据中提取需要判断的实际结果&#xff0c;再设置预期结果&#xff0c;两者进行比较得出断言结果。 下面首先介绍JSON与JSON…

springboot01

目录 新建Maven工程&#xff0c;什么都不选 ​pom.xml加上 新建包top.cjz.controller 新建类HelloController ​新建类HelloApplication ​运行浏览器访问 新建Maven工程&#xff0c;什么都不选 pom.xml加上 <!--springboot工程需要继承的父工程--> <parent…

第六次面试、第一次复试

第六面&#xff1a; hr迟到&#xff0c;说是搞错了以为线下&#xff0c;我打电话过去才开始&#xff0c;问我想电话面还是视频&#xff0c;果断电话面 自我介绍 介绍了一下公司的工作 ................. 项目拷打&#xff1a; grpc数据如何传输的如何调用两个接口如何获取…