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

算法笔记(十)——队列+宽搜

文章目录

  • N 叉数的层序遍历
  • 二叉树的锯齿形层序遍历
  • 二叉树最大宽度
  • 在每个树行中找最大值

BFS是图上最基础、最重要的搜索算法之一;
每次都尝试访问同一层的节点如果同一层都访问完了,再访问下一层

BFS基本框架

void bfs(起始点)
{将起始点放入队列中;标记起点已访问;while(队列不为空){访问队列中首元素;删除队首元素;for(队首元素所有相邻点){if(该点未被访问过且合法)将该点加入队列末尾; }}宽搜结束; 
} 

N 叉数的层序遍历

题目:N 叉数的层序遍历

在这里插入图片描述
思路

  • BFS(宽搜)
  • 创建vector<vector<int>> ret来保存结果;
  • 创建queue<Node*> q来将根节点入队,如果根节点为空则直接返回空的ret
  • 当队列不为空的时候一直循环:
    • 获取当前队列大小
    • vector<int> tmp来统计本层节点
    • 出队头元素,保存在tmp中,若其孩子节点非空,则进入队列
    • 每层节点出队后,将其保存在tmp中的节点,push_backret

C++代码

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution 
{
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> ret; // 存储层序遍历的结果queue<Node*> q; // 层序遍历需要的队列if(root == nullptr) return ret;q.push(root);while(q.size()){int n = q.size(); // 本层元素个数vector<int> tmp;  // 统计本层节点for(int i = 0; i < n; i++){Node* t = q.front();q.pop();tmp.push_back(t->val);for(Node* child : t->children) // 让下一次节点入队{if(child != nullptr)q.push(child);}}ret.push_back(tmp);}return ret;}
};

二叉树的锯齿形层序遍历

题目:二叉树的锯齿形层序遍历

在这里插入图片描述
思路1

  • 和上一题的思路一样,我们先封装一个函数vector<vector<int>> levelOrder(TreeNode *root)正常层序遍历该二叉树,将其结果存储在vector<vector<int>> ret
  • 再对结果ret进行逆序,当为偶数层时,对其结果进行逆序;

C++代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution
{
public:vector<vector<int>> zigzagLevelOrder(TreeNode *root){vector<vector<int>> ret = levelOrder(root);// 偶数层时,对其结果进行逆序for (int i = 1; i < ret.size(); i += 2)reverse(ret[i].begin(), ret[i].end());return ret;}vector<vector<int>> levelOrder(TreeNode *root){vector<vector<int>> ret;if (!root)return ret;queue<TreeNode* > q;q.push(root);while (q.size()){int n = q.size();vector<int> tmp;for(int i = 0; i < n; i++){TreeNode* t = q.front();tmp.push_back(t->val);q.pop();if(t->left) q.push(t->left);if(t->right) q.push(t->right);}ret.push_back(tmp);}return ret;}
};

思路2
我们也可以添加一个标记位flag,当奇数层时,正常添加到结果数组,偶数层时,逆序后进入结果数组

C++代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
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 = 0; // 标志层数while (q.size()){flag++;int n = q.size();vector<int> tmp;for(int i = 0; i < n; i++){TreeNode* t = q.front();tmp.push_back(t->val);q.pop();if(t->left) q.push(t->left);if(t->right) q.push(t->right);}if(flag % 2 == 0) reverse(tmp.begin(), tmp.end()); // 偶数层逆序后再进入结果数组ret.push_back(tmp);}return ret;}};

二叉树最大宽度

题目:二叉树最大宽度

在这里插入图片描述

思路
对于数组存储的二叉树,我们知道

  • 父亲节点下标为i(从一开始)。则,
  • 左孩子下标为2 * i
  • 左孩子下标为2 * i + 1

如果二叉树非常不平衡,节点全部在右侧,空节点也进行插入操作去计算的话,空间是远远不够的

  • 我们可以通过计算每层插入节点的头和尾下标差值,并使用vector来模拟队列操作
  • 每次都覆盖前一层,以防超出内存
  • 计算差值,使用无符号整型,避免数据溢出
  • 定义一个队列 vector<pair<TreeNode*, unsigned int>> q;// 数组模拟队列,元素包含一个二叉树节点指针和该节点在完全二叉树中的编号
  • 将根节点和其对应编号 1 放入队列 q
  • 进入循环,获取当前层数收尾元素,并且更新当前最大宽度
  • 创建一个临时队列tmp来更新q

C++代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution 
{
public:int widthOfBinaryTree(TreeNode* root) {vector<pair<TreeNode*, unsigned int>> q; // 数组模拟队列q.push_back({root, 1});unsigned int ret = 0;while(q.size()){auto& [x1, y1] = q[0];auto& [x2, y2] = q.back();ret = max(ret, y2 - y1 + 1);// 下一层进临时队vector<pair<TreeNode*, unsigned int>> tmp;for(auto& [x, y] : q){if(x->left) tmp.push_back({x->left, y * 2});if(x->right) tmp.push_back({x->right, y * 2 + 1});}q = tmp;}    return ret;}
};

在每个树行中找最大值

题目:在每个树行中找最大值

在这里插入图片描述

思路

利用层序遍历,统计每层最大值;

C++代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution 
{
public:vector<int> largestValues(TreeNode* root) {vector<int> ret;if(root == nullptr) return ret;queue<TreeNode*> q;q.push(root);while(q.size()){int n = q.size();int _max = INT_MIN;for(int i = 0; i < n; i++){auto t = q.front();q.pop();_max = max(_max, t->val);if(t->left) q.push(t->left);if(t->right) q.push(t->right);}ret.push_back(_max);}return ret;}
};

相关文章:

算法笔记(十)——队列+宽搜

文章目录 N 叉数的层序遍历二叉树的锯齿形层序遍历二叉树最大宽度在每个树行中找最大值 BFS是图上最基础、最重要的搜索算法之一&#xff1b; 每次都尝试访问同一层的节点如果同一层都访问完了&#xff0c;再访问下一层 BFS基本框架 void bfs(起始点) {将起始点放入队列中;标记…...

webpack配置全面讲解【完整篇】

文章目录 前言webpack 核心包&#xff1a;配置文件导出三种方式&#xff1a;在线配置 webpack配置文件解析&#xff1a;入口&#xff08;Entry&#xff09;&#xff1a;输出&#xff08;Output&#xff09;&#xff1a;加载器&#xff08;Loaders&#xff09;&#xff1a;插件&…...

十、kotlin的协程

协程 基本概念定义组成挂起和恢复结构化并发协程构建器作用域构建器挂起函数阻塞与非阻塞runBlocking全局协程像守护线程 Job的生命周期 常用函数延时和等待启动和取消启动取消 暂停 协程启动调度器启动方式启动模式线程上下文继承的定义继承的公式 协程取消与超时取消挂起点取…...

vscode qt 最新开发环境配置, 基于最新插件 Qt All Extensions Pack

qt 之前发布了vscode qt offical ,但是最新更新中将其升级改为了几个不同的插件&#xff0c;功能更强大 1. 前置条件 qt 已安装 2. 插件安装 打开vscode 插件安装&#xff0c;搜索qt 会看到很多qt插件&#xff0c;直接选择Qt All Extensions Pack 安装 会安装qt环境所需的…...

【MySQL】Ubuntu环境下MySQL的安装与卸载

目录 1.MYSQL的安装 2.MySQL的登录 3.MYSQL的卸载 4.设置配置文件 1.MYSQL的安装 首先我们要看看我们环境里面有没有已经安装好的MySQL 我们发现是默认是没有的。 我们还可以通过下面这个命令来确认有没有mysql的安装包 首先我们得知道我们当前的系统版本是什么 lsb_…...

C# StringBuilder类:高效构建和修改字符串的利器

C# 中的 StringBuilder 类是一个可变的字符序列&#xff0c;用于高效地构建和修改字符串。与字符串&#xff08;string&#xff09;不同&#xff0c;字符串在 C# 中是不可变的&#xff0c;这意味着每次修改字符串&#xff08;如拼接、替换等操作&#xff09;时&#xff0c;都会…...

AVL平衡树(AVL Tree)

**场景&#xff1a;课堂讨论** --- **小明&#xff08;ESFP学生&#xff09;**&#xff1a;张老师&#xff0c;为什么AVL树&#xff08;AVL Tree&#xff09;中的旋转操作这么重要&#xff1f;感觉只是节点的移动&#xff0c;有没有什么实际意义&#xff1f; **张老师&#…...

【python实操】python小程序之两数取大值以及login登录

引言 python小程序之两数取大值以及login登录 文章目录 引言一、两数取大值1.1 题目1.2 代码1.3 代码解释 二、login登录2.1 题目2.2 代码2.3 代码解释 三、思考3.1 两数取大值3.2 login登录 一、两数取大值 1.1 题目 定义一个函数my_max&#xff0c;包含两个参数, 函数的作用…...

Pikachu-File Inclusion-远程文件包含

远程文件包含漏洞 是指能够包含远程服务器上的文件并执行。由于远程服务器的文件是我们可控的&#xff0c;因此漏洞一旦存在&#xff0c;危害性会很大。但远程文件包含漏洞的利用条件较为苛刻&#xff1b;因此&#xff0c;在web应用系统的功能设计上尽量不要让前端用户直接传变…...

TIM(Timer)定时器的原理

一、介绍 硬件定时器的工作原理基于时钟信号源提供稳定的时钟信号作为计时器的基准。计数器从预设值开始计数&#xff0c;每当时钟信号到达时计数器递增。当计数器达到预设值时&#xff0c;定时器会触发一个中断信号通知中断控制器处理相应的中断服务程序。在中断服务程序中&a…...

Microsoft Visual Studio有多油饼

#1 Microsoft Visual Studio C 2023&#xff1a; 必须安装在C盘 为啥&#xff1f; 安其他盘能亖啊&#xff1f; 真有病 #2 Microsoft Visual Studio C 2013&#xff1a; 每个硬盘必须都腾出至少8个G的空间 不是我安在这个盘不就是为了其他盘没空间吗&#xff1f; 合着…...

Golang | Leetcode Golang题解之第452题用最少数量的箭引爆气球

题目&#xff1a; 题解&#xff1a; func findMinArrowShots(points [][]int) int {if len(points) 0 {return 0}sort.Slice(points, func(i, j int) bool { return points[i][1] < points[j][1] })maxRight : points[0][1]ans : 1for _, p : range points {if p[0] > …...

Python 从入门到实战35(进程-multiprocessing模块)

我们的目标是&#xff1a;通过这一套资料学习下来&#xff0c;可以熟练掌握python基础&#xff0c;然后结合经典实例、实践相结合&#xff0c;使我们完全掌握python&#xff0c;并做到独立完成项目开发的能力。 上篇文章我们讨论了turtle库绘制图画操作的相关知识。今天学习一下…...

“米哈游悄然布局未来科技:入股星海图,共绘具身智能机器人新篇章“

米哈游悄然入股具身智能机器人公司:技术布局与未来展望 近日,米哈游阿尔戈科技有限公司宣布入股具身智能机器人公司星海图,这一消息在行业内引起了广泛关注。米哈游,这家以游戏开发而闻名的企业,近年来正逐步扩大其在人工智能和新兴科技领域的投资布局,此次入股星海图正是…...

基于spring boot的篮球论坛系统

作者&#xff1a;计算机搬砖家 开发技术&#xff1a;SpringBoot、php、Python、小程序、SSM、Vue、MySQL、JSP、ElementUI等&#xff0c;“文末源码”。 专栏推荐&#xff1a;SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;Java精选实战项…...

华夏ERP账号密码泄露漏洞

漏洞描述 华夏ERP账号密码泄露漏洞 漏洞复现 FOFA "jshERP-boot" POC IP/jshERP-boot/user/getAllList;.ico...

Android问题笔记五十:构建错误-AAPT2 aapt2-7.0.2-7396180-windows Daemon

Unity3D特效百例案例项目实战源码Android-Unity实战问题汇总游戏脚本-辅助自动化Android控件全解手册再战Android系列Scratch编程案例软考全系列Unity3D学习专栏蓝桥系列ChatGPT和AIGC &#x1f449;关于作者 专注于Android/Unity和各种游戏开发技巧&#xff0c;以及各种资源分…...

CAD 3dsmax maya等autodesk系列专用卸载修复工具AutoRemove,一键完全彻底卸载删除软件的专用卸载工具

AutoRemove 是一款功能强大的软件卸载工具&#xff0c;专门设计用于彻底清除Autodesk系列软件&#xff0c;如AutoCAD、3ds Max、Revit、Maya、Inventor、Navisworks、civil 3d、sketchbook、Architecture、Electrical、Mechanical、、等&#xff0c;从您的系统中。它通过深度清…...

python中的函数介绍

文章目录 1.函数1.1 语法格式1.2 函数参数1.3 函数的返回值1.4 变量作用域1.5 函数的执行过程1.6 链式调用1.7 嵌套调用1.8 函数栈帧1.9 函数递归1.10 参数默认值1.11 关键词参数 1.函数 无论是编程中的函数还是数学中的函数&#xff0c;本质都是差不多的&#xff0c;丢给函数…...

LinuxO(1)调度算法

概念 在Linux中&#xff0c;O(1)调度算法是一种进程调度算法。O(1)表示算法的时间复杂度是常数级别的&#xff0c;与系统中的进程数量无关。 运行队列结构 他采用了两个运行队列&#xff0c;一个活动队列和一个过期队列。活动队列中的进程是有资格获取CPU时间片的进程&#x…...

数据库分批入库

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

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

使用SSE解决获取状态不一致问题

使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件&#xff0c;这个上传文件是整体功能的一部分&#xff0c;文件在上传的过程中…...

EasyRTC音视频实时通话功能在WebRTC与智能硬件整合中的应用与优势

一、WebRTC与智能硬件整合趋势​ 随着物联网和实时通信需求的爆发式增长&#xff0c;WebRTC作为开源实时通信技术&#xff0c;为浏览器与移动应用提供免插件的音视频通信能力&#xff0c;在智能硬件领域的融合应用已成必然趋势。智能硬件不再局限于单一功能&#xff0c;对实时…...

【PX4飞控】mavros gps相关话题分析,经纬度海拔获取方法,卫星数锁定状态获取方法

使用 ROS1-Noetic 和 mavros v1.20.1&#xff0c; 携带经纬度海拔的话题主要有三个&#xff1a; /mavros/global_position/raw/fix/mavros/gpsstatus/gps1/raw/mavros/global_position/global 查看 mavros 源码&#xff0c;来分析他们的发布过程。发现前两个话题都对应了同一…...

ubuntu清理垃圾

windows和ubuntu 双系统&#xff0c;ubuntu 150GB&#xff0c;开发用&#xff0c;基本不装太多软件。但是磁盘基本用完。 1、查看home目录 sudo du -h -d 1 $HOME | grep -v K 上面的命令查看$HOME一级目录大小&#xff0c;发现 .cache 有26GB&#xff0c;.local 有几个GB&am…...

EC2安装WebRTC sdk-c环境、构建、编译

1、登录新的ec2实例&#xff0c;证书可以跟之前的实例用一个&#xff1a; ssh -v -i ~/Documents/cert/qa.pem ec2-user70.xxx.165.xxx 2、按照sdk-c demo中readme的描述开始安装环境&#xff1a; https://github.com/awslabs/amazon-kinesis-video-streams-webrtc-sdk-c 2…...

Ansible+Zabbix-agent2快速实现对多主机监控

ansible Ansible 是一款开源的自动化工具&#xff0c;用于配置管理&#xff08;Configuration Management&#xff09;、应用部署&#xff08;Application Deployment&#xff09;、任务自动化&#xff08;Task Automation&#xff09;和编排&#xff08;Orchestration&#xf…...

.Net Framework 4/C# 面向对象编程进阶

一、继承 (一)使用继承 子类可以继承父类原有的属性和方法,也可以增加原来父类不具备的属性和方法,或者直接重写父类中的某些方法。 C# 中使用“:”来表示两个类的继承。子类不能访问父类的私有成员,但是可以访问其公有成员,即只要使用 public 声明类成员,就既可以让一…...