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

BFS 求解 最小高度树 【妙用】

310. 最小高度树

链接 :题目链接

  • 思路
    • 常规解法是树形dp,两个dfs解决,这里不再赘述
    • 新颖解法bfs,而且实现更加简单,大体思路就是每次都从叶子节点一步步往中心爬,最后一批留在队列中的节点就为本题意的答案,具体实现思路就是每次更新叶子节点,也就是把之前的叶子节点扔掉,然后和它相连的节点度数减一产生新的叶子节点。

代码


class Solution {
public:vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {if(n == 1) return {0};vector<int> out(n+10);// 统计每个点的出度vector<vector<int>> e(n+10);for(auto i : edges){int a = i[0];int b = i[1];out[a] ++, out[b] ++;e[b].push_back(a);// 建立邻接表e[a].push_back(b);}vector<int> res;queue<int> q;for(int i = 0; i < n; i ++){if(out[i] == 1)// 先让出度为1的点入队{q.push(i);}}while(q.size()){res.clear();// res 存储当下遍历完的节点int num = q.size();for(int i = 0; i < num; i ++){int x = q.front();q.pop();res.push_back(x);for(auto it : e[x]){out[it] --;// 与该点连接的点 出度减一if(out[it] == 1)// 添加新的"叶子节点"{q.push(it);}}}}return res;}
};

思路来自 大佬小鑫

相关文章:

BFS 求解 最小高度树 【妙用】

310. 最小高度树 链接 &#xff1a;题目链接 思路 常规解法是树形dp&#xff0c;两个dfs解决&#xff0c;这里不再赘述新颖解法bfs&#xff0c;而且实现更加简单&#xff0c;大体思路就是每次都从叶子节点一步步往中心爬&#xff0c;最后一批留在队列中的节点就为本题意的答案…...

【机器学习300问】36、什么是集成学习?

一、什么是集成学习&#xff1f; &#xff08;1&#xff09;它的出现是为了解决什么问题&#xff1f; 提高准确性&#xff1a;单个模型可能对某些数据敏感或者有概念偏见&#xff0c;而集成多个模型可以提高预测的准确性。让模型变稳定&#xff1a;一些模型&#xff0c;如决策…...

Stargo 管理部署 Starrocks 集群

配置主机间 ssh 互信 ssh-copy-id hadoop02 ssh-copy-id hadoop03配置系统参数 ############################ Swap检查 ############################ echo 0 | sudo tee /proc/sys/vm/swappiness########################### 内核参数检查 ########################## echo…...

CI/CD实战-git工具使用 1

版本控制系统 本地版本控制系统 集中化的版本控制系统 分布式版本控制系统 git官网文档&#xff1a;https://git-scm.com/book/zh/v2 Git 有三种状态&#xff1a;已提交&#xff08;committed&#xff09;、已修改&#xff08;modified&#xff09; 和 已暂存&#xff08;sta…...

Linux中udp服务端,客户端的开发

UDP通信相关函数&#xff1a; ssize_t recvfrom(int sockfd, void *buf, size_t len, int flags, struct sockaddr *src_addr, socklen_t *addrlen); 函数说明&#xff1a;接收信息 参数说明&#xff1a;sockfd:套接字buf:要接收的缓冲区len:缓冲区…...

1.python安装

1.检查是否已经安装python 打开cmd 输入 python --version查看是否有返回版本,没有返回则环境变量未设置好,或者未安装 2.下载安转python https://www.python.org/downloads/windows/ 勾选配置环境变量路径 安装成功...

【Flink SQL】Flink SQL 基础概念(三):SQL 动态表 连续查询

《Flink SQL 基础概念》系列&#xff0c;共包含以下 5 篇文章&#xff1a; Flink SQL 基础概念&#xff08;一&#xff09;&#xff1a;SQL & Table 运行环境、基本概念及常用 APIFlink SQL 基础概念&#xff08;二&#xff09;&#xff1a;数据类型Flink SQL 基础概念&am…...

科研绘图一:箱线图(添加贝赛尔曲线)

R语言绘图系列—箱线图贝赛尔曲线 &#xff08;一&#xff09;: 科研绘图一&#xff1a;箱线图&#xff08;添加贝赛尔曲线&#xff09; 文章目录 R语言绘图系列---箱线图贝赛尔曲线&#xff08;一&#xff09;: 科研绘图一&#xff1a;箱线图&#xff08;添加贝赛尔曲线&…...

最佳实践:Swagger 自动生成 Api 文档

自动生成 API 文档的好处不言而喻&#xff0c;它可以提供给你的团队或者外部协作者&#xff0c;方便 API 使用者准确地调用到你的 API。为了降低手动编写文档带来的错误&#xff0c;很多 API 开发者会偏向于寻找一些好的方法来自动生成 API 文档。本文将会介绍一些常用的文档生…...

搬砖。。。

0搬砖 - 蓝桥云课 (lanqiao.cn) 问题描述 这天&#xff0c;小明在搬砖 他一共有n块砖他发现第砖的重量为w价值为i。他突然想从这些砖中选一些出来从下到上堆成一座塔,并且对于塔中的每一块砖来说&#xff0c;它上面所有砖的重量和不能超过它自身的价值。 他想知道这样堆成的塔的…...

【论文笔记合集】Transformers in Time Series A Survey综述总结

本文作者&#xff1a; slience_me 文章目录 Transformers in Time Series A Survey综述总结1 Introduction2 Transformer的组成Preliminaries of the Transformer2.1 Vanilla Transformer2.2 输入编码和位置编码 Input Encoding and Positional Encoding绝对位置编码 Absolute …...

HarmonyOS(二十)——管理应用拥有的状态之LocalStorage(页面级UI状态存储)

LocalStorage是页面级的UI状态存储&#xff0c;通过Entry装饰器接收的参数可以在页面内共享同一个LocalStorage实例。LocalStorage也可以在UIAbility实例内&#xff0c;在页面间共享状态。 本文仅介绍LocalStorage使用场景和相关的装饰器&#xff1a;LocalStorageProp和LocalS…...

Linux系统安全②SNAT与DNAT

目录 一.SNAT 1.定义 2.实验环境准备 &#xff08;1&#xff09;三台服务器&#xff1a;PC1客户端、PC2网关、PC3服务端。 &#xff08;2&#xff09;硬件要求&#xff1a;PC1和PC3均只需一块网卡、PC2需要2块网卡 &#xff08;3&#xff09;网络模式要求&#xff1a;PC1…...

【运维】StarRocks数据迁移到新集群(针对于集群互通、不互通的情况)

文章目录 一. 迁移整体思路1. 对于新旧集群互通的情况2. 对于新旧集群不互通的情况二、迁移过程(两个集群互通的情况)1. 备份过程1.1. 通过mysqlclient与starrocks进行关联1.2. 创建仓库与minio建立联系1.3. 备份数据到minio2. 迁移过程2.1. 通过mysqlclient与starrocks进行关…...

facebook个人广告账户充值方式有哪些?看这一篇就够了

可以使用虚拟信用卡进行充值&#xff0c;也可以使用虚拟卡绑定paypal进行充值 点击获取虚拟卡 开卡步骤如下图 Facebook如何添加支付方式 1.前往支付设置。 2.在支付方式版块&#xff0c;点击添加支付方式。 3.选择要添加的支付方式&#xff0c;填写相关信息&#xff0c;然…...

蓝桥杯算法练习系统—作物杂交【第十一届】【省赛】【C组】

问题描述 作物杂交是作物栽培中重要的一步。已知有 N 种作物(编号 1 至 N )&#xff0c;第 i 种作物从播种到成熟的时间为 Ti。 作物之间两两可以进行杂交&#xff0c;杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天&#xff0c;作物 B 种植时间为 7 天&#xff0…...

java组合模式揭秘:如何构建可扩展的树形结构

组合模式&#xff08;Composite Pattern&#xff09;是一种结构型设计模式&#xff0c;它允许将对象组合成树形结构以表示整体/部分层次结构。组合模式使得客户端可以统一对待单个对象和组合对象&#xff0c;从而使得客户端可以处理更复杂的结构。 组合模式的主要组成部分包括&…...

pycharm 历史版本下载地址

pycharm 历史版本下载地址 老版本能用就行&#xff0c;不需要搞最新的&#xff0c;当然了&#xff0c;有些小伙伴就是喜欢新的&#xff08;最先吃螃蟹&#xff09; 博主就不搞最新了&#xff0c;哈哈 上菜&#xff1a; https://www.jetbrains.com/pycharm/download/other.html…...

Day39:安全开发-JavaEE应用SpringBoot框架Actuator监控泄漏Swagger自动化

目录 SpringBoot-监控系统-Actuator SpringBoot-接口系统-Swagger 思维导图 Java知识点&#xff1a; 功能&#xff1a;数据库操作&#xff0c;文件操作&#xff0c;序列化数据&#xff0c;身份验证&#xff0c;框架开发&#xff0c;第三方组件使用等. 框架库&#xff1a;MyB…...

VsCode免密登录

创建本地密匙 按下WinR输入cmd&#xff0c;输入 ssh-keygen -t rsa然后连续回车直到结束 找到Your public key has been saved in C:\Users\Administrator/.ssh/id_rsa.pub&#xff0c;每个人都不一样找到密匙所在地 打开id_rsa.pub这个文件&#xff0c;可以用记事本打开&am…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

GraphQL 实战篇:Apollo Client 配置与缓存

GraphQL 实战篇&#xff1a;Apollo Client 配置与缓存 上一篇&#xff1a;GraphQL 入门篇&#xff1a;基础查询语法 依旧和上一篇的笔记一样&#xff0c;主实操&#xff0c;没啥过多的细节讲解&#xff0c;代码具体在&#xff1a; https://github.com/GoldenaArcher/graphql…...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...