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

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...