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

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...