LeetCode_拓扑排序_困难_2603.收集树中金币

目录

  • 1.题目
  • 2.思路
  • 3.代码实现(Java)

1.题目

给你一个 n 个节点的无向无根树,节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ,其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ,其中 coins[i] 可能为 0 也可能为 1,1 表示节点 i 处有一个金币。一开始,你需要选择树中任意一个节点出发。你可以执行下述操作任意次:

  • 收集距离当前节点距离为 2 以内的所有金币,或者
  • 移动到树中一个相邻节点。

你需要收集树中所有的金币,并且回到出发节点,请你返回最少经过的边数。如果你多次经过一条边,每一次经过都会给答案加一。

示例 1:
在这里插入图片描述

输入:coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
输出:2
解释:从节点 2 出发,收集节点 0 处的金币,移动到节点 3 ,收集节点 5 处的金币,然后移动回节点 2。

示例 2:

在这里插入图片描述

输入:coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
输出:2
解释:从节点 0 出发,收集节点 4 和 3 处的金币,移动到节点 2 处,收集节点 7 处的金币,移动回节点 0 。

提示:
n == coins.length
1 <= n <= 3 * 104
0 <= coins[i] <= 1
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges 表示一棵合法的树。

2.思路

(1)两次拓扑排序
思路参考本题官方题解。

3.代码实现(Java)

//思路1————两次拓扑排序
class Solution {public int collectTheCoins(int[] coins, int[][] edges) {int n = coins.length;//图的邻接表List<Integer>[] graph = new ArrayList[n];for (int i = 0; i < n; ++i) {graph[i] = new ArrayList<>();}//计算每个节点的度int[] degree = new int[n];for (int[] edge : edges) {int x = edge[0], y = edge[1];graph[x].add(y);graph[y].add(x);++degree[x];++degree[y];}//将入度为 1 且无金币的叶子节点放入队中Queue<Integer> queue = new ArrayDeque<>();for (int i = 0; i < n; ++i) {if (degree[i] == 1 && coins[i] == 0) {queue.offer(i);}}int rest = n;while (!queue.isEmpty()) {int u = queue.poll();--degree[u];--rest;for (int v : graph[u]) {--degree[v];if (degree[v] == 1 && coins[v] == 0) {queue.offer(v);}}}//删除树中所有的叶子节点,连续删除 2 次for (int x = 0; x < 2; ++x) {queue = new ArrayDeque<Integer>();for (int i = 0; i < n; ++i) {if (degree[i] == 1) {queue.offer(i);}}while (!queue.isEmpty()) {int u = queue.poll();--degree[u];--rest;for (int v : graph[u]) {--degree[v];}}}return rest == 0 ? 0 : (rest - 1) * 2;}
}

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

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

相关文章

10分钟设置免费海外远程桌面

前言 本教程将向您介绍如何使用 Amazon Lightsail 服务的免费套餐轻松搭建属于您的远程桌面。依托于 Amazon 全球可用区&#xff0c;您可以在世界各地搭建符合您配置需求的远程桌面。 本教程需要先拥有亚马逊云科技海外账户。现在注册亚马逊云科技账户可以享受12个月免费套餐…

《向量数据库指南》——文心大模型+Milvus向量数据库搭建AI原生应用

亲爱的科技探险家们和代码魔法师们: 未来的钟声已经敲响,预示着一场极度炫酷的虚拟现实游戏即将展开。从初期简单的智能识别,到设计师级别的图纸设计,生成式AI技术(Generative AI)以其独特理念和创新模式重塑了传统内容生产效率和交互模式,在无数领域展现着非凡的才华。…

清易低功耗智能雨量监测站概述

一、低功耗智能雨量监测站概述产品概述 低功耗智能雨量监测站基于智能传感、无线通信、智能处理与智能控制等物联网技术的开发&#xff0c;利用智能传感技术&#xff0c;通过传感器测量降雨量&#xff0c;并使用物联网进行传输。无需专门的通信线路&#xff0c;在联网的状态下…

简单的手机电脑无线传输方案@固定android生成ftp的IP地址(android@windows)

文章目录 abstractwindows浏览android文件环境准备客户端软件无线网络链接步骤其他方法 手机浏览电脑文件公网局域网everythingpython http.server 高级:固定android设备IP准备检查模块是否生效 windows 访问ftp服务器快捷方式命令行方式双击启动方式普通快捷方式映射新的网络位…

zabbix网络管理安装教程

安装&#xff1a; apt install zabbix-server-mysql zabbix-frontend-php zabbix-nginx-conf zabbix-sql-scripts zabbix-agent 参考资源&#xff1a; 官网&#xff1a; 下载&#xff1a; 其它&#xff1a; 常用指令&#xff1a; 目标与应用价值&#xff1a; 部署难点&#…

【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码

冒泡排序原理 每次比较两个相邻的元素&#xff0c;将较大的元素交换至右端 冒泡排序执行过程输出效果 冒泡排序实现思路 每次冒泡排序操作都会将相邻的两个元素进行比较&#xff0c;看是否满足大小关系要求&#xff0c;如果不满足&#xff0c;就交换这两个相邻元素的次序&…

在已知的二维坐标里找到最接近的点

一、业务场景 最近在研发的项目&#xff0c;在做可视化层&#xff0c;在全球地图上&#xff0c;对我们的国家的陆地地图经纬度按照步长为1的间隔做了二维处理。在得到一组整数的点位信息后&#xff0c;需要将我们已有的数据库数据(业务项目)按照地址的经纬度&#xff0c;映射到…

GUN、MIT、Apache、BSD、MPL各种开源协议介绍和区别

文章目录 目前主流的开源协议GNU通用公共许可证&#xff08;GNU General Public License&#xff0c;GPL&#xff09;MIT许可证Apache许可证BSD许可证MPL Mozilla公共许可证&#xff08;Mozilla Public License&#xff0c;MPL&#xff09; 各种主流开源协议的区别GNU通用公共许…

玩转Nginx

Nginx是什么 Nginx&#xff08;engine x&#xff09;是一款的Web服务器、反向代理服务器&#xff0c;能够实现前端Web应用的部署、请求反向代理及负载均衡处理等功能。 特点 轻量&#xff0c;占用内存少高可靠高并发、高性能可扩展性好支持热部署BSD许可证(开源、可修改再发…

使用FFmpeg+ubuntu系统转化flac无损音频为mp3

功能需求如上题,我们来具体的操作一下: 1.先在ubuntu上面安装FFmpeg:sudo apt install ffmpeg 2.进入有flac音频文件的目录使用下述命令: ffmpeg -i test.FLAC -c:a libmp3lame -q:a 2 output.mp3 3.如果没有什么意外的话,你就能看到你的文件夹里面已经有转化好的mp3文件了 批…

Python —— excel文件操作(超详细)

背景 很多公司还是用excel去管理测试用例的&#xff0c;所以为了减少重复繁琐的导出导出工作&#xff0c;学会如何用代码操作excel表格很实用~ 1、读取excel文件基本步骤 1、操作excel的一些库 1、xlrd&#xff1a;读取库&#xff0c;xlwt&#xff1a;写入&#xff0c;现在…

Golang Linux 安装与环境变量配置

下载 Go 二进制包 wget https://dl.google.com/go/go1.21.1.linux-amd64.tar.gz 解压文件并将其移至 /usr/local 目录 sudo tar -C /usr/local -xzf go1.20.1.linux-amd64.tar.gz -C 选项解压文件到 /usr/local 目录&#xff0c;查看 /usr/local/go 目录的内容 将 Go 二进…

token登录的实现

token登录的实现 我这种token只是简单的实现token&#xff0c;就是后端利用UUID 生成简单随机码&#xff0c;利用随机码作为在Redis中的键&#xff0c;然后存储的用户信息作为值&#xff0c;在每次合理请求的时候对token的有效时间进行刷新&#xff08;利用拦截器&#xff09;&…

IP风险查询:抵御DDoS攻击和CC攻击的关键一步

随着互联网的普及&#xff0c;网络攻击变得越来越普遍和复杂&#xff0c;对企业和个人的网络安全构成了重大威胁。其中&#xff0c;DDoS&#xff08;分布式拒绝服务&#xff09;攻击和CC&#xff08;网络连接&#xff09;攻击是两种常见且具有破坏性的攻击类型&#xff0c;它们…

python实现命令tree的效果

把所有的文档都传到了git上,但是内容过多找起来不方便,突发奇想如果能在readme中,递归列出所有文件同时添加上对应的地址,这样只需要搜索到对应的文件点击就能跳转过去了… 列出文件总得有个显示格式,所以就按照tree的来了… 用python实现命令tree的效果 首先,这是tree的效果…

【力扣每日一题】2023.9.21 收集树中金币

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 题目给我们一棵树&#xff0c;不过这棵树不是普通的树&#xff0c;而是无向无根树。给我们一个二维数组表示节点之间的连接关系&#xff…

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…