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

【算法】图论

头像
⭐️个人主页:@小羊
⭐️所属专栏:Linux
很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~

动图描述

目录

  • 持续更新中...
    • 1、DFS
    • 2、BFS
      • N 叉树的层序遍历
      • 二叉树的锯齿形层序遍历
      • 二叉树最大宽度
    • 3、多源BFS
      • 腐烂的苹果
    • 4、拓扑排序


持续更新中…


1、DFS

单词搜索

class Solution 
{int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};bool check[101][101] = {};// 标记数组,防止上下左右找的时候重复遍历int m, n;
public:bool exist(vector<string>& board, string word){m = board.size(), n = board[0].size();for (int i = 0; i < m; i++)for (int j = 0; j <n; j++)if (board[i][j] == word[0]){check[i][j] = true;// 找到第一个字符了,开始找下一个字符if (dfs(board, word, i, j, 1)) return true;check[i][j] = false;}return false;}bool dfs(vector<string>& board, string& word, int i, int j, int pos){// 找到单词结尾就返回if (pos == word.size()) return true;for (int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && board[x][y] == word[pos]){check[x][y] = true;if (dfs(board, word, x, y, pos + 1)) return true;check[x][y] = false;}}// 如果走到这里说明没有进递归,也就是四个方位都没找到字符return false;}
};

2、BFS

通常利用队列first in first out的特点,统计出每层的q.size()以遍历每一层。

N 叉树的层序遍历

  • N 叉树的层序遍历

在这里插入图片描述

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> ret;if (root == nullptr) return ret;queue<Node*> q;q.push(root);while (!q.empty()){vector<int> tmp;int size = q.size();while (size--){tmp.push_back(q.front()->val);for (auto e : q.front()->children){q.push(e);}q.pop(); // 利用父节点把子节点全部插入队列后再删除父节点}ret.push_back(tmp);}return ret;}
};

二叉树的锯齿形层序遍历

  • 二叉树的锯齿形层序遍历

在这里插入图片描述

遇到二叉树的题一定注意判断有没有左右子节点,不然很容易对空节点解引用。

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ret;if (root == nullptr) return ret;queue<TreeNode*> q;q.push(root);int flag = 1;while (!q.empty()){int size = q.size();vector<int> tmp;while (size--){auto t = q.front();tmp.push_back(t->val);if (t->left) q.push(t->left);if (t->right) q.push(t->right);q.pop();}flag *= -1;if (flag > 0) reverse(tmp.begin(), tmp.end());ret.push_back(tmp);}return ret;}
};

二叉树最大宽度

  • 二叉树最大宽度


3、多源BFS

腐烂的苹果

  • 腐烂的苹果

在这里插入图片描述

class Solution {int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};bool vis[1001][1001] = {};int m, n;queue<int> q;
public:int rotApple(vector<vector<int> >& grid) {m = grid.size(), n = grid[0].size();for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (grid[i][j] == 2 && !vis[i][j]){vis[i][j] = true;bfs(grid, i, j);}}int bfs(vector<vector<int>>& grid, int i, int j){while (!q.empty()){}for (int k = 0; k < 4; k++){}}
};

4、拓扑排序


本篇文章的分享就到这里了,如果您觉得在本文有所收获,还请留下您的三连支持哦~

头像

相关文章:

【算法】图论

⭐️个人主页&#xff1a;小羊 ⭐️所属专栏&#xff1a;Linux 很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~ 目录 持续更新中...1、DFS2、BFSN 叉树的层序遍历二叉树的锯齿形层序遍历二叉树最大宽度 3、多源BFS腐烂的苹果 4、拓扑排序 持续更新中…...

ADQ32 5G采集卡

ADQ32是一款高端12位双通道数据采集板&#xff0c;针对高通量科学应用进行了优化。ADQ32具有以下特性: 一个和两个模拟输入通道包括每通道5和2.5 GSPS7GB/s的持续数据传输速率至GPU7GB/秒的持续数据传输速率两个外部触发器通用输入/输出&#xff08;GPIO&#xff09;开放式FPG…...

机器人领域专业名词汇总

1. 电机与驱动 电机类型 DC Motor&#xff08;直流电机&#xff09;&#xff1a;通过直流电源驱动的电机。Stepper Motor&#xff08;步进电机&#xff09;&#xff1a;通过脉冲信号控制旋转角度的电机。Servo Motor&#xff08;伺服电机&#xff09;&#xff1a;带有反馈控制的…...

拆解 “ES 已死“ 伪命题:Agentic RAG 时代搜索引擎的终极形态

作者&#xff1a;来自 Elastic 李捷 xxx&#xff1a;“ES已死&#xff0c;#%#……” 我&#xff1a;&#xff1f;&#xff1f;&#xff1f; 最近&#xff0c;某厂商发了一堆公关文章&#xff0c;翻来覆去地炒作 “ES 已死”&#xff0c;“放弃 ES”。这哪是什么正经的技术文章&…...

eNSP中路由器的CON/AUX接口、GE Combo接口、Mini USB接口、USB接口、WAN侧uplink接口、FE接口、GE接口介绍

路由器常见接口的详细介绍及其应用示例&#xff1a; 1. CON/AUX 接口 全称&#xff1a;Console/Auxiliary&#xff08;控制台/辅助接口&#xff09;作用&#xff1a; CON&#xff08;Console&#xff09;&#xff1a;通过命令行界面&#xff08;CLI&#xff09;直接配置路由器…...

平面的四种方程及一些应用

平面的四种方程及一些应用 点法式方程一般式方程三点式方程截距式方程一些应用已知平面方程&#xff0c;找出平面上不共线的三个点 点法式方程 平面经过点 ( x 0 , y 0 , z 0 ) (x_0,y_0,z_0) (x0​,y0​,z0​)且法向量为 ( a , b , c ) (a,b,c) (a,b,c)&#xff0c;则平面的点…...

记录一个SQL自动执行的html页面

在实际工作场景中&#xff0c;需要运用到大量SQL语句更新业务逻辑&#xff0c;对程序员本身&#xff0c;写好的sql语句执行没有多大问题&#xff08;图1&#xff09;&#xff0c;但是对于普通用户来说还是有操作难度的。因此我们需要构建一个HTML页面&#xff08;图2&#xff0…...

SpringBoot——Maven篇

Spring Boot 是一个用于快速开发基于 Spring 框架的应用程序的工具。它具有许多特性&#xff0c;其中一些重要的特性包括&#xff1a; 1. 自动配置&#xff1a;Spring Boot 提供了自动配置的机制&#xff0c;可以根据应用程序的依赖和环境自动配置应用程序的各种组件&#xff…...

数据批处理(队列方式)

数据批处理&#xff08;队列方式&#xff09; public class DataProcessor {private static final int THREAD_COUNT 4;private static final int QUEUE_SIZE 10;private LinkedBlockingQueue<Data> queue new LinkedBlockingQueue<>(QUEUE_SIZE);public DataP…...

从零开始搭建搜索推荐系统(五十四)多路召回之万剑归宗

聊的不止技术。跟着小帅写代码&#xff0c;还原和技术大牛一对一真实对话&#xff0c;剖析真实项目筑成的一砖一瓦&#xff0c;了解最新最及时的资讯信息&#xff0c;还可以学到日常撩妹小技巧哦&#xff0c;让我们开始探索主人公小帅的职场生涯吧&#xff01; &#xff08;PS…...

c++介绍函数指针 十

指针代表内存中地址标识符&#xff0c;变量&#xff0c;数组都是存储内存中的数据。所以可以获得它们的地址&#xff0c;用指针来表示这块内存。 如图输出内存中的地址。 对于一个函数来说&#xff0c;也是内存中存储这段数据&#xff0c;所以我们也可以获取函数的地址。 函数…...

redis数据库

一、redis数据库介绍 NoSQL Not Only SQL 非关系型数据库 1、关系型数据库与非关系型数据库的区别 非关系型数据库性能高、速度快、支持高并发连接 1、非关系型数据库基于内存存储数据 2、摒弃了关系型数据的约束限制 3、采用o1算法进行设计开发 2、作用 关系型数…...

关于 NoC 中数据安全传输的设计与实现的详细介绍

片上网络&#xff08;Network-on-Chip&#xff0c;NoC&#xff09;作为一种新兴的片上通信架构&#xff0c;解决了传统总线架构在大规模集成电路设计中面临的诸多问题。然而&#xff0c;随着芯片系统的复杂性和应用场景的多样化&#xff0c;NoC 中数据安全传输变得至关重要。以…...

OpenGL(4)着色器

文章目录 一、着色器1、什么是着色器&#xff1f;2、着色器类型2.1、顶点着色器&#xff08;Vertex Shader&#xff09;2.2、片段着色器&#xff08;Fragment Shader&#xff09; 3、着色器属性3.1、layout 属性3.2、in 属性3.3、out 属性3.4、总结 4、示例 前言&#xff1a; 在…...

PHP批量去除Bom头的方法

检查的代码&#xff1a; <?php$dir __DIR__; $files new RecursiveIteratorIterator(new RecursiveDirectoryIterator($dir));foreach ($files as $file) {if ($file->isFile() && pathinfo($file, PATHINFO_EXTENSION) php) {$content file_get_contents(…...

51单片机的keil c51软件安装教程

Keil&#xff08;C51&#xff09;介绍、下载、安装与注册_keil c51-CSDN博客 参考 安装 不一定是这个大小&#xff0c;也可以下载别的版本KEID C51 注册 加入芯片型号 …...

JavaScript基本知识

文章目录 一、JavaScript基础1.变量&#xff08;重点&#xff09;1-1 定义变量及赋值1-2 变量的命名规则和命名规范判断数据类型&#xff1a; 2.数据类型转换2-1 其他数据类型转成数值2-2 其他数据类型转成字符串2-3 其他数据类型转成布尔 3.函数3-1函数定义阶段3-2函数调用阶段…...

导数,积分及常用公式

导数定义&#xff1a; ​ 求导是数学计算中的一个计算方法&#xff0c;它的定义就是&#xff0c;当自变量的增量趋于零时&#xff0c;因变量的增量与自变量的增量之商的极限。在一个函数存在导数时&#xff0c;称这个函数可导或者可微分。可导的函数一定连续。不连续的函数一定…...

鸿蒙应用开发—ZDbUtil高效使用数据库

文章目录 介绍下载安装基本使用注解TableIdColumnOneToOne 使用方法定义实体类初始化数据库并根据被Table注解的类创建表创建表查数据插入数据删除数据清空数据 参考 介绍 ZDbUtil是一款基于SQLite的鸿蒙数据库框架&#xff0c;通过注解标注实体类与属性&#xff0c;让数据更能…...

强化学习(赵世钰版)-学习笔记(7.时序差分学习)

本章是课程算法与方法中的第四章&#xff0c;介绍的时序差分学习算法是基于随机近似方法设计的强化学习方法&#xff0c;也是model-free的方法。 时序差分算法是一种近似估计策略状态值的算法&#xff0c;具体的形式如下&#xff1a; 本质上是在当前t时刻&#xff0c;被访问到的…...

正则表达式入门及常用的正则表达式

正则表达式&#xff08;Regular Expression&#xff0c;简称 Regex&#xff09;是一种强大的文本处理工具&#xff0c;用于匹配、查找和替换字符串中的特定模式。以下是入门指南和常用正则表达式示例&#xff1a; 一、正则表达式入门 1. 基本语法 符号说明示例.匹配任意单个字…...

大白话如何在 Vue 项目中进行路由懒加载?

大白话如何在 Vue 项目中进行路由懒加载&#xff1f; 在 Vue 项目里&#xff0c;路由懒加载是种很实用的技术&#xff0c;它能让你在需要的时候再去加载对应的路由组件&#xff0c;而不是在项目启动时就把所有组件都加载进来&#xff0c;这样能加快项目的启动速度。下面就详细…...

手动实现一个RTTI系统

在 C 中&#xff0c;RTTI&#xff08;Runtime Type Information&#xff0c;运行时类型信息&#xff09;是一组允许程序在运行时获取对象类型信息的机制 。虽然C通过虚接口的方式提供了良好的抽象&#xff0c;但是对于一个复杂的系统&#xff0c;过于依赖抽象而忽略业务的复杂性…...

智能化水利监管:无人机视频在违章行为识别中的应用

随着我国经济社会的快速发展&#xff0c;水利工程建设规模不断扩大&#xff0c;但随之而来的违章建设行为也日益增多。传统的人工巡查方式效率低下&#xff0c;难以满足当前监管需求。无人机技术以其灵活性和高效性&#xff0c;为水利工程建设监管提供了新的解决方案。本文将探…...

力扣练习之确定两个字符串是否接近

目录 题目&#xff1a; 题解&#xff1a; 详细题解 题目&#xff1a; 如果可以使用以下操作从一个字符串得到另一个字符串&#xff0c;则认为两个字符串 接近 &#xff1a; 操作 1&#xff1a;交换任意两个 现有 字符。 例如&#xff0c;abcde -> aecdb 操作 2&#xff1…...

Word 小黑第21套

对应大猫22 设置表格为页面的80%&#xff1a;表布局 -属性 -表格 指定宽度80% 度量单位改成百分比 段落组 -中文版式 在表格上下方留一行空段&#xff08;如果表格太大改一下样式&#xff09;插入横线 边框线 &#xff08;右击横线 -图片 修改样式&#xff09; 段落 -取消对于…...

mingw32编译ffmpeg

ffmpeg https://gitee.com/mirrors/ffmpeg.git 使用msys2的mingw32 pacman -S mingw-w64-x86_64-toolchain compile ./confiure --enable-static --disable-shared --enable-gpl --target-oswin32 mingw32-make -j4 提示编译错误&#xff0c;msys2里面的路径是/d/tools/msys2…...

设计模式C++

针对一些经典的常见的场景, 给定了一些对应的解决方案&#xff0c;这个就叫设计模式。 设计模式的作用&#xff1a;使代码的可重用性高&#xff0c;可读性强&#xff0c;灵活性好&#xff0c;可维护性强。 设计原则&#xff1a; 单一职责原则&#xff1a;一个类只做一方面的…...

使用 Excel 实现绩效看板的自动化

引言 在日常工作中&#xff0c;团队的绩效监控和管理是确保项目顺利进行的重要环节。然而&#xff0c;面临着以下问题&#xff1a; ​数据分散&#xff1a;系统中的数据难以汇总&#xff0c;缺乏一个宏观的团队执行情况视图。​看板缺失&#xff1a;系统本身可能无法提供合适…...

ngx_openssl_conf_t

ngx_openssl_conf_t 定义在 src\event\ngx_event_openssl.c typedef struct {ngx_uint_t engine; /* unsigned engine:1; */ } ngx_openssl_conf_t; 1. 这个结构体的目的是存储与 OpenSSL 引擎相关的配置信息。 2. engine 字段用于标识是否启用 OpenSSL 的硬件加速引擎…...

深度学习环境配置指令大全

文章目录 环境配置官网/博客合集清华镜像站anaconda官网pytorch官网pytorch历史库官网pytorch与cuda对应版本下载博客torch与torchvision与python对应关系python与pytorch对应关系 环境相关创建环境激活环境退出环境删除环境检查环境冲突 安装相关安装requirementsconda安装con…...

Netty启动源码NioEventLoop剖析accept剖析read剖析write剖析

学习链接 NIO&Netty - 专栏 Netty核心技术十–Netty 核心源码剖析Netty核心技术九–TCP 粘包和拆包及解决方案Netty核心技术七–Google ProtobufNetty核心技术六–Netty核心模块组件Netty核心技术五–Netty高性能架构设计 聊聊Netty那些事儿 - 专栏 一文搞懂Netty发送数…...

<03.13>八股文补充知识

import java.lang.reflect.*; public class Main {public static void main(String[] args) throws Exception {// 获取 Class 对象//1. 通过类字面量Class<?> clazz Person.class;//2 通过对象实例化String str "Hello";Class<?> clazz_str str.ge…...

[HUBUCTF 2022 新生赛]messy_traffic

下载附件 看到文件类型直接用wireshark打开&#xff0c;对MySQL协议进行追踪流&#xff0c;并没有什么发现&#xff0c;后面对NO.437发现有用信息&#xff0c;http追踪流 发现**system(‘cat passwd.txt’);**这里是在打开查看passwd.txt&#xff0c;密码是"SignUpForHUBU…...

条款1:理解模版性别推导

目录 问题引出 情况1&#xff1a;ParamType是个指针或引用&#xff0c;但不是个万能引用。 情况2&#xff1a;ParamType是个万能引用 情况3&#xff1a;ParamType既非指针也非引用 问题引出 函数模板大致形如&#xff1a; template<typename T> void f(ParamType p…...

kafka连问

1&#xff0c;kafka多消费者指部署多个服务消费节点吗 2&#xff0c;多个消费节点自动组成消费组吗 3&#xff0c;消费者组与多消费节点关系 4&#xff0c;一个分区&#xff0c;多个消费者&#xff0c;可以保证有序消费吗 5&#xff0c;kafka如何实现顺序消费&#xff0c;一…...

Linux中基础开发工具详细介绍

目录 软件包管理器什么是软件包Linux软件生态 yum具体操作查看软件包安装软件卸载软件注意事项 编辑器VimLinux编辑器-vim使用vim的基本概念快速编辑的指令 编译器gcc/g背景知识gcc编译选项预处理(进行宏替换)编译&#xff08;生成汇编&#xff09;汇编&#xff08;生成机器可识…...

浅谈时钟启动和Systemlnit函数

时钟是STM32的关键&#xff0c;是整个系统的心脏&#xff0c;时钟如何启动&#xff0c;时钟源如何选择&#xff0c;各个参数如何设置&#xff0c;我们从源码来简单分析一下时钟的启动函数Systemlnit&#xff08;&#xff09;。 Systemlnit函数简介 我们先来看一下源程序的注释…...

社交软件频繁更新,UI 设计在其中扮演什么角色?

在当今数字化时代&#xff0c;社交软件已成为人们日常生活中不可或缺的一部分。随着科技的飞速发展和用户需求的不断变化&#xff0c;社交软件更新频率日益加快。在这频繁更新的背后&#xff0c;UI 设计扮演着至关重要的角色&#xff0c;它如同社交软件的 “门面担当” 与 “交…...

SQLMesh 系列教程:解锁SQLMesh的宏与变量魔法

在数据库流水线开发中&#xff0c;代码复用与动态配置是提升效率的核心诉求。SQLMesh以其独特的宏系统与用户定义变量机制&#xff0c;重新定义了SQL生成的灵活性。与传统模板引擎不同&#xff0c;SQLMesh的宏并非简单的字符串替换&#xff0c;而是基于语义理解的智能代码重构—…...

React篇之three渲染

需求&#xff1a;拖拽右侧面板&#xff0c;里面的three模型能够自适应 import { useEffect, useState, useRef } from react import ./App.css import * as THREE from three; import { GLTFLoader } from three/addons/loaders/GLTFLoader.js; import { debounce } from loda…...

PHP与前端框架的无缝集成:最佳实践与案例分析

PHP与前端框架的无缝集成&#xff1a;最佳实践与案例分析 在现代Web开发中&#xff0c;PHP作为后端语言与前端框架的集成已成为一种常见的开发模式。无论是传统的MVC架构&#xff0c;还是现代的SPA&#xff08;单页应用&#xff09;&#xff0c;PHP与前端框架的无缝集成能够显…...

Redis内存淘汰策略

Redis 是一种高性能的键值存储系统&#xff0c;广泛用于缓存、消息队列等场景。由于 Redis 数据存储在内存中&#xff0c;而内存资源有限&#xff0c;因此需要内存淘汰策略来管理内存的使用。Redis 提供了多种内存淘汰策略&#xff0c;可以根据不同的应用场景选择合适的策略。 …...

Facebook 的框架及技术栈

一、前端框架与技术 React.js 及其生态系统 核心原理与特点 React.js 是 Facebook 开源的用于构建用户界面的 JavaScript 库。它的核心概念是组件化&#xff0c;将用户界面拆分成一个个独立的、可复用的组件。每个组件都有自己的状态&#xff08;state&#xff09;和属性&#…...

QT中的布局管理

在 Qt 中&#xff0c;布局管理器&#xff08;如 QHBoxLayout 和 QVBoxLayout&#xff09;的构造函数可以接受一个 QWidget* 参数&#xff0c;用于指定该布局的父控件。如果指定了父控件&#xff0c;布局会自动将其管理的控件添加到父控件中。 在你的代码中&#xff0c;QHBoxLa…...

如何学习VBA_3.2.20:DTP与Datepicker实现日期的输入

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的劳动效率&#xff0c;而且可以提高数据处理的准确度。我推出的VBA系列教程共九套和一部VBA汉英手册&#xff0c;现在已经全部完成&#xff0c;希望大家利用、学习。 如果…...

在 LaTeX 中强制表格位于页面顶部

在 LaTeX 中强制表格位于页面顶部&#xff0c;可以通过以下 多种方法结合使用&#xff0c;按优先级推荐&#xff1a; 方法 1&#xff1a;使用 [!t] 位置限定符 原理&#xff1a;通过 [!t] 强制 LaTeX 优先将表格放置在页面顶部&#xff08;Top&#xff09;&#xff0c;! 表示忽…...

dify+mysql的诗词助手

目录 数据库表结构&#xff1a; 数据库查询的http服务搭建&#xff1a; 流程引擎搭建&#xff1a; 开始&#xff0c; HTTP查询数据库&#xff0c; LLM数据分析&#xff0c; 直接回复&#xff0c; 效果测试&#xff1a; 下载链接&#xff1a; 数据库表结构&#xff1a;…...

PyTorch 入门学习

目录 PyTorch 定义 核心作用 应用场景 Pytorch 基本语法 1. 张量的创建 2. 张量的类型转换 3. 张量数值计算 4. 张量运算函数 5. 张量索引操作 6. 张量形状操作 7. 张量拼接操作 8. 自动微分模块 9. 案例-线性回归案例 PyTorch 定义 PyTorch 是一个基于 Python 深…...

【视频】SRS将RTMP转WebRTC、HLS流;获取RTSP转其它流

1、安装依赖库 sudo apt install tclsh sudo apt install cmake sudo apt install autotools-dev automake m4 perl sudo apt install libtool2、源码安装 1)下载源码 https://github.com/ossrs/srs/releases/tag/v5.0-r32)配置、编译 ./configure && make -j83、…...