当前位置: 首页 > 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…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...