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

【LeetCode热题100】队列+宽搜

这篇博客是关于队列+宽搜的几道题,主要包括N叉树的层序遍历、二叉树的锯齿形层序遍历、二叉树最大宽度、在每个数行中找最大值。

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> ret;if(!root) return ret;queue<Node*> q;q.push(root);while(q.size()){int num = q.size();  //先求出本层的元素个数vector<int> tmp;  //统计本层的节点while(num--){Node* top = q.front();q.pop();tmp.push_back(top->val);for(auto e : top->children){if(e != nullptr)q.push(e);}}ret.push_back(tmp);}return ret;}
};

题目分析:这道题我们需要层序遍历,需要借助一个队列实现,首先将第一层节点放进队列,然后出队列,在出队列后,把它的孩子节点都push到队列中,再依次把这几个孩子节点出队列,每一个节点出队列后,都要马上把它的孩子节点push到队列。为了知道每层有几个节点,在每一层出队列前,需要统计队列里的元素个数。

 

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ret;if(!root) return ret;queue<TreeNode*> q;q.push(root);int flag = 1;while(q.size()){int sz = q.size();vector<int> tmp;for(int i = 0 ; i < sz ; i++){TreeNode* top = q.front();q.pop();tmp.push_back(top->val);if(top->left) q.push(top->left);if(top->right) q.push(top->right);}if(flag % 2 == 0){reverse(tmp.begin(), tmp.end());}ret.push_back(tmp);flag++;}return ret;}
};

题目分析:仍然是使用队列来存放节点,和上一题不同的是,在得到偶数层的队列后,需要将其逆序一下,可以通过创建一个变量来判断奇偶层。

class Solution {
public:int widthOfBinaryTree(TreeNode* root) {vector<pair<TreeNode*,unsigned int>> queue;unsigned int ret = 0;queue.push_back({root, 1});while(queue.size()){auto& [x1, y1] = queue[0];auto& [x2, y2] = queue.back();ret = max(ret, y2 - y1 + 1);vector<pair<TreeNode*,unsigned int>> tmp;for(auto& [x, y] : queue){if(x->left) tmp.push_back({x->left, 2*y});if(x->right) tmp.push_back({x->right, 2*y + 1}); }queue = tmp;} return ret;}
};

题目分析:这道题我们可以使用数组存储二叉树的方式,给节点编号,数组的类型为pair<TreeNode*,int>,int为这个节点的编号,一层的两端节点编号相减+1就是这层的宽度。

需要注意的是,下标可能溢出,所以不能用int存储节点编号,而是用unsigned int 存储。

class Solution {
public:vector<int> largestValues(TreeNode* root) {queue<TreeNode*> q;vector<int> ret;if(!root) return ret;q.push(root);// ret.push_back(root->val);while(q.size()){int size = q.size();int m = INT_MIN;while(size--){TreeNode* top = q.front();q.pop();m = max(m, top->val);if(top->left) q.push(top->left);if(top->right) q.push(top->right);}ret.push_back(m);}return ret;}
};

题目分析:很简单,利用层序遍历,统计每一层的最大值。

相关文章:

【LeetCode热题100】队列+宽搜

这篇博客是关于队列宽搜的几道题&#xff0c;主要包括N叉树的层序遍历、二叉树的锯齿形层序遍历、二叉树最大宽度、在每个数行中找最大值。 class Solution { public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> ret;if(!root) …...

【阵列信号处理】相干信号和非相干信号生成

文章目录 一、总结二、知识点相干&#xff08;coherent&#xff09;和非相干&#xff08;incoherent&#xff09;信号相干信号生成代码 相关信号&#xff08;correlated signal&#xff09;相关信号生成代码 正交信号定义 本文记录博主的科研日记。如果对博主的其他文章感兴趣&…...

React 组件生命周期

React 组件生命周期 React 组件生命周期是React框架中一个核心概念,它描述了一个组件从创建到销毁的过程。理解组件生命周期对于高效开发React应用至关重要,因为它允许开发者在一个组件的不同阶段执行特定的逻辑。本文将详细介绍React组件的生命周期方法,并解释它们在组件的…...

Kylin Server V10 下基于Sentinel(哨兵)实现Redis高可用集群

一、什么是哨兵模式 Redis Sentinel 是一个分布式系统,为 Redis 提供高可用性解决方案。可以在一个架构中运行多个 Sentinel 进程(progress)这些进程使用流言协议(gossip protocols)来接收关于主服务器是否下线信息,并使用投票协议(agreement protocols)来决定是否执行…...

07-Making a Bar Chart with D3.js and SVG

课程链接 Curran的课程&#xff0c;通过 D3.js 的 scaleLinear, max, scaleBand, axisLeft, axisBottom&#xff0c;根据 .csv 文件生成一个横向柱状图。 【注】如果想造csv数据&#xff0c;可以使用通义千问&#xff0c;关于LinearScale与BandScale不懂的地方也可以在通义千…...

硅谷甄选前端项目环境配置笔记

此教程来自于尚硅谷 文章目录 **此教程来自于尚硅谷**硅谷甄选运营平台一、搭建后台管理系统模板1.1项目初始化1.1.1环境准备1.1.2初始化项目 1.2项目配置一、eslint配置1.1vue3环境代码校验插件1.2修改.eslintrc.cjs配置文件1.3.eslintignore忽略文件1.4运行脚本 二、配置**pr…...

6.7机器学习期末复习题

空间 样本空间 就是属性的所有可能情况&#xff0c;包括了一切可能出现或不可能出现的所有样本情况 版本空间&假设空间 假设空间就是在样本空间的基础上&#xff0c;给所有属性都加了一个通配符&#xff0c;表示任意即可&#xff1b;以及加上了一个空集&#xff0c;表示…...

1123--日期类

目录 一 java 1. Date类 2. calendar类 3. 第三代日期类‘ 3.1 常用方法 3.2 格式化操作 一 java 1. Date类 2. calendar类 3. 第三代日期类‘ 3.1 常用方法 3.2 格式化操作...

YOLOV5 /onnx模型转换成rknn

上两篇文章讲述了pytorch模型下best.pt转换成onnx模型&#xff0c;以及将onnx进行简化成为best-sim.onnx, 接下来这篇文章讲述如何将onnx模型转换成rknn模型&#xff0c;转换成该模型是为了在rk3568上运行 1.创建share文件夹 文件夹包含以下文件best-sim.onnx,rknn-tookit2-…...

Echarts+VUE饼图的使用(基础使用、多个饼图功能、单组饼图对应颜色使用)

安装&#xff1a;npm install echarts --save 配置:main.js // 引入echarts import * as echarts from echarts Vue.prototype.$echarts echarts一、基础饼图&#xff08;直接拷贝就能出效果&#xff09; <div class"big-box" ref"demoEhart"><…...

刘铁猛C#入门 026 重写与多态

类的继承 类成员的“横向扩展”(成员越来越多)类成员的“纵向扩展”(行为改变&#xff0c;版本增高)类成员的隐藏(不常用)重写与隐藏的发生条件&#xff1a;函数成员&#xff0c;可见&#xff0c;签名一致 函数成员:方法 、属性可见&#xff1a;父类修饰符是public protected …...

《筑牢安全防线:培养 C++安全编程思维习惯之道》

在当今数字化飞速发展的时代&#xff0c;软件安全的重要性已提升到前所未有的高度。C作为一种广泛应用于系统开发、游戏制作、高性能计算等众多领域的编程语言&#xff0c;其程序的安全性更是关乎重大。培养 C安全编程的思维习惯&#xff0c;不仅是开发者个人能力提升的关键&am…...

《TCP/IP网络编程》学习笔记 | Chapter 16:关于 I/O 流分离的其他内容

《TCP/IP网络编程》学习笔记 | Chapter 16&#xff1a;关于 I/O 流分离的其他内容 《TCP/IP网络编程》学习笔记 | Chapter 16&#xff1a;关于 I/O 流分离的其他内容分离 I/O 流2 次 I/O 流分离分离「流」的好处「流」分离带来的 EOF 问题 文件描述符的的复制和半关闭终止「流」…...

单片机学习笔记 5. 数码管静态显示

更多单片机学习笔记&#xff1a;单片机学习笔记 1. 点亮一个LED灯单片机学习笔记 2. LED灯闪烁单片机学习笔记 3. LED灯流水灯单片机学习笔记 4. 蜂鸣器滴~滴~滴~ 目录 0、实现的功能 1、Keil工程 1-1 数码管显示原理 1-2 静态与动态显示 1-3 74HC573锁存器的工作原理 1-…...

ValueError: not enough values to unpack (expected 2, got 1) 解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…...

java基础知识(常用类)

一、包装类&#xff08;Wrapper) &#xff08;1&#xff09;包装类与基本数据的转换 装箱&#xff1a;基本类型->包装类型 拆箱&#xff1a;包装类型->基本类型 java5以后是自动装箱和拆箱的方式&#xff0c;自动装箱底层调用的是valueOf方法&#xff0c;比如Integer.…...

Selenium+Java(19):使用IDEA的Selenium插件辅助超快速编写Pages

前言 或是惊叹于Selenium对于IDEA的支持已经达到了这样的地步,又或是由于这个好用的小工具的入口就在那里,它已经陪伴了我这么久,而我这么久的时间却都没有发现它。在突然发现这个功能的一瞬间,真的是喜悦感爆棚,于是赶快写下了这篇文章。希望可以帮助到其他同样在做UI自动…...

决策树分类算法【sklearn/决策树分裂指标/鸢尾花分类实战】

决策树分类算法 1. 什么是决策树&#xff1f;2. DecisionTreeClassifier的使用&#xff08;sklearn&#xff09;2.1 算例介绍2.2 构建决策树并实现可视化 3. 决策树分裂指标3.1 信息熵&#xff08;ID3&#xff09;3.2 信息增益3.3 基尼指数&#xff08;CART&#xff09; 4. 代码…...

深入理解 Spring Boot 的 WebApplicationType

1. 前言 在 Spring Boot 应用程序启动过程中,WebApplicationType 是一个重要的概念,它决定了应用程序是以 Web 应用程序的形式运行还是以非 Web 应用程序的形式运行。本文将详细探讨 WebApplicationType 的工作机制及其在实际项目中的应用。 2. 什么是 WebApplicationType?…...

摄影:相机控色

摄影&#xff1a;相机控色 白平衡&#xff08;White Balance&#xff09;白平衡的作用&#xff1a; 白平衡的使用环境色温下相机色温下总结 白平衡偏移与包围白平衡包围 影调 白平衡&#xff08;White Balance&#xff09; 人眼看到的白色&#xff1a;会自动适应环境光线。 相…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...