当前位置: 首页 > news >正文

OJ练习第178题——收集树中金币

收集树中金币

力扣链接:2603. 收集树中金币

题目描述

给你一个 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 。

官解思路

在这里插入图片描述
这一步可以使用基于广度优先搜索的拓扑排序解决。我们首先将所有「叶节点」加入队列中,随后不断从队列中取出节点,将它标记为删除,并判断其唯一相邻的节点是否变为「叶节点」。如果是,就将相邻的节点也加入队列中。
在这里插入图片描述
这一步同样可以使用基于广度优先搜索的拓扑排序解决。我们进行 222 次如下的操作:首先将所有「叶节点」加入初始队列中,随后不断从初始队列中取出节点,将它标记为删除。
在这里插入图片描述

Java代码

class Solution {public int collectTheCoins(int[] coins, int[][] edges) {int n = coins.length;List<Integer>[] g = new List[n];for(int i = 0; i < n; i++) {g[i] = new ArrayList<Integer>();}int[] degree = new int[n];for(int[] edge : edges) {int x = edge[0], y = edge[1];g[x].add(y);g[y].add(x);degree[x]++;degree[y]++;}int rest = n;/* 删除树中所有无金币的叶子节点,直到树中所有的叶子节点都是含有金币的 */Queue<Integer> queue = new ArrayDeque<Integer>();for(int i = 0; i < n; i++) {if(degree[i] == 1 && coins[i] == 0) {queue.offer(i);}}while(!queue.isEmpty()) {int u = queue.poll();degree[u]--;rest--;for(int v : g[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 : g[u]) {degree[v]--;}}}return rest == 0 ? 0 : (rest - 1) * 2;}
}

相关文章:

OJ练习第178题——收集树中金币

收集树中金币 力扣链接&#xff1a;2603. 收集树中金币 题目描述 给你一个 n 个节点的无向无根树&#xff0c;节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges &#xff0c;其中 edges[i] [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给…...

uni-app打包iOS ipa文件后不上架App store为用户提供下载解决过程记录

写在前面&#xff0c;itms-services协议是什么 itms-services协议是苹果提供的一种让iOS应用在用户设备上无线安装或升级的协议。 具体来说: itms-services表示iOS应用无线安装服务的URL方案,格式为:itms-services://?actiondownload-manifest&urlMANIFEST_URL其中MANIF…...

MySQL学习系列(2)-每天学习10个知识

目录 1. INNER JOIN 和 ON 子句2. 死锁3. SELECT * 和 SELECT column1, column24. 数据库的视图5. MySQL的触发器类型6. MySQL表的备份和恢复7. MySQL存储引擎8. 索引优化9. MySQL中的子查询10. 使用连接&#xff08;JOIN&#xff09;从多个表中检索数据 &#x1f44d; 点赞&am…...

黑马JVM总结(十四)

&#xff08;1&#xff09;分代回收_1 Java虚拟机都是结合前面几种算法&#xff0c;让他们协同工作&#xff0c;具体实现是虚拟机里面一个叫做分代的垃圾回收机制&#xff0c;把我们堆内存大的区域划分为两块新生代、老年代 新生代有划分为伊甸园、幸存区Form、幸存区To 为什…...

vue项目升级webpack

vue项目升级webpack 目录 1. vue项目中影响webpack版本的是什么 2.理解package.json中库前缀^和~区别 3.升级webpack4到5操作 1. vue项目中影响webpack版本的是什么 答案是&#xff1a;vue/cli-service版本 2.理解package.json中库前缀^和~区别 x.y.z x代表大版本&#xf…...

ubuntu的root用户修改密码失败

解决如下&#xff1a; 查看文件属性是否有a或i lsattr /etc/group /etc/passwd /etc/shadow 移除a和i的属性权限 chattr -ai /etc/group /etc/passwd /etc/shadow 再次使用passwd进行修改密码&#xff0c;就成功了...

C++---链表

1、链表 1.1、链表的结构 每个链表开头都有一个头指针Head尾节点的指针域为NULL&#xff0c;用于判断此列表是否结束 如果一个链表开始就为NULL&#xff0c;那么该链表为空链表 链表中的先后不代表在真实内存中的位置&#xff0c;只是单纯的逻辑上关系 1.2、创建链表 我们首…...

Unity使用Mirror制作局域网的同步

1.脚本布置.参考tank那个demo制作 1.新建空物体,为管理脚本的物体:manager,挂载NetworkManager,kcpTransport,NetworkManagerHud. 2.设置玩家出生点,spawnPoint,设置好初始化的position的位置(*),挂载NetworkStartPosition的脚本 3.新建Player的预制体,挂载NetworkIdentity,Ne…...

算法 N皇后问题-(递归回溯)

牛客网 BM59. 解题思路&#xff1a; 行列、斜叉不在一条直线上。 命令行为 row, 列为col, row 从0开始递归直到最后一行&#xff0c;列从0开始遍历&#xff0c;直到最后一列&#xff0c;中间每一步记录或清除位置状态&#xff0c;状态分为 m1[col] 1, m2[row-col] 1, m3[r…...

个人博客搭建记录

个人博客地址&#xff1a;www.jiasun.top 使用github pagehexo搭建&#xff0c;主题为fluid&#xff0c;搭建步骤参照&#xff1a;Github hexo 实现自己的个人博客、配置主题&#xff08;超详细&#xff09; 主题&#xff1a;https://hexo.fluid-dev.com/ 搭建时的问题&…...

下载vscode 更新

将下载地址的主地址加入一下镜像网址 http://vscode.cdn.azure.cn下面是访问页面 http://vscode.cdn.azure.cn/stable/abd2f3db4bdb28f9e95536dfa84d8479f1eb312d/VSCodeUserSetup-x64-1.82.2.exe...

std::async简单使用

std::async介绍并使用 std::async是C11引入的一个用于异步执行函数或函数对象的工具。它可以用于并行地执行函数&#xff0c;并在需要时获取函数的返回值。下面是一个简单的示例&#xff0c;演示了如何使用std::async&#xff1a; #include <iostream> #include <fu…...

【编程实践】在VS studio中配置Eigen库

1 介绍 Eigen库是C标准模板库&#xff0c;能够进行向量运算、矩阵运算、矢量运算、数值分析等操作&#xff0c;并且包含相应的运算算法。 Eigen官方地址: 地址 可在官网下载指定版本的压缩包&#xff0c;将压缩包解压至后面配置的“附件包含目录”中。 2 配置 2.1 VS studi…...

SQLite 3.43 发布,性能大提升!

前言 SQLite是一种被广泛运用的嵌入式关系型数据库管理系统&#xff0c;最新发布的SQLite 3.43版本带来了一个重要的改进&#xff0c;大幅提升了对JSON数据的处理性能&#xff0c;达到了之前的两倍。 主要更新 添加对 Contentless-Delete FTS5 索引的支持。这是 FTS5 全文搜索…...

数据中心液冷服务器详情说明

目录 前言 何为液冷服务器&#xff1f; 为什么需要液冷&#xff1f; 1.数据中心降低PUE的需求 2.政策导向 3.芯片热功率已经达到风冷散热极限 4.液冷比热远大于空气 液冷VS风冷&#xff0c;区别在哪&#xff1f; 1.液冷服务器跟风冷服务器的区别 2.液冷数据中心跟风冷…...

Openresty(二十二)ngx.balance和balance_by_lua终结篇

一 灰度发布铺垫 ① init_by_lua* init_by_lua init_by_lua_block 特点: 在openresty start、reload、restart时执行,属于master init 阶段机制&#xff1a; nginx master 主进程加载配置文件时&#xff0c;运行全局Lua VM级别上的参数指定的Lua代码场景&#xff1a; …...

Docker注入环境变量且设置多个环境变量

方式一 运行docker命令修改 在运行docker时&#xff0c;直接使用-e或–env&#xff0c;输入需要改变的变量 例如&#xff1a;springboot配置文件如下,可注入环境变量启动端口SERVER_PORT&#xff0c;以及启动配置文件NODE_ENV:dev server:port: ${SERVER_PORT:8400} spring…...

代码随想录二刷Day 15

102. Binary Tree Level Order Traversal vector<int>() it is basically constructor of std::vector class and will create a new empty vector. You can also mention the size of required vector in brackets. 访问二维vector的元素: 如果指定外层和内层向量的大…...

Node.js环境安装与服务设置,结合内网穿透随时随地公网访问!

文章目录 前言1.安装Node.js环境2.创建node.js服务3. 访问node.js 服务4.内网穿透4.1 安装配置cpolar内网穿透4.2 创建隧道映射本地端口 5.固定公网地址 前言 Node.js 是能够在服务器端运行 JavaScript 的开放源代码、跨平台运行环境。Node.js 由 OpenJS Foundation&#xff0…...

八、数据类型转换

数据类型转换 1.数据类型转换1.1.隐式类型转换1.2.显式类型转换1.3.训练11.4.训练2 —————————————————————————————————————————————————— 1.数据类型转换 类型转换是将一个值从一种类型更改为另一种类型的过程。例如&…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构

React 实战项目&#xff1a;微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇&#xff01;在前 29 篇文章中&#xff0c;我们从 React 的基础概念逐步深入到高级技巧&#xff0c;涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...

如何做好一份技术文档?从规划到实践的完整指南

如何做好一份技术文档&#xff1f;从规划到实践的完整指南 &#x1f31f; 嗨&#xff0c;我是IRpickstars&#xff01; &#x1f30c; 总有一行代码&#xff0c;能点亮万千星辰。 &#x1f50d; 在技术的宇宙中&#xff0c;我愿做永不停歇的探索者。 ✨ 用代码丈量世界&…...

基于小程序老人监护管理系统源码数据库文档

摘 要 近年来&#xff0c;随着我国人口老龄化问题日益严重&#xff0c;独居和居住养老机构的的老年人数量越来越多。而随着老年人数量的逐步增长&#xff0c;随之而来的是日益突出的老年人问题&#xff0c;尤其是老年人的健康问题&#xff0c;尤其是老年人产生健康问题后&…...