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

BFS 算法专题(四):多源 BFS

目录

1. 01 矩阵

1.1 算法原理

1.2 算法代码

2. 飞地的数量

2.1 算法原理

2.2 算法代码

3. 地图中的最高点

3.1 算法原理

3.2 算法代码

4. 地图分析

4.1 算法原理

4.2 算法代码


1. 01 矩阵

. - 力扣(LeetCode)

1.1 算法原理

  1. 采用 BFS + 正难则反 的解题思想, 把所有为 0 的位置为起点, 把所有为 1 的位置为终点.
  2. 将所有为 0 的位置加入队列中, 一层一层往外扩, 将为 1 的位置, 修改为距离 0 的最短步数

细节点: 建立一个二维数组 int[][] distance, distinct[i][j] 中存的是 [i, j] 位置距离 0 的最短路径.

dest数组的作用:

  1. 不需使用 boolean 数组做标记 => 将原数组中为 1 的位置, 在 dest 中初始化为 -1(特殊标记)
  2. 不需使用 size 记录每层中元素个数 => 借助 dest[a][b] 中的值即可(dest[x, y] = dest[a, b] + 1)
  3. 不需使用 step 记录扩展的层数 => 借助 dest[a][b] 中的值即可(dest[x, y] = dest[a, b] + 1)

1.2 算法代码

class Solution {public int[][] updateMatrix(int[][] mat) {int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};int m = mat.length, n = mat[0].length;int[][] dist = new int[m][n];Queue<int[]> q = new LinkedList<>();for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(mat[i][j] == 0) q.offer(new int[]{i, j});else dist[i][j] = -1;}}// 以为 0 位置为起点, 一层一层往外扩while(!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];for(int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) {dist[x][y] = dist[a][b] + 1;q.offer(new int[]{x, y});}}}return dist;}
}

2. 飞地的数量

. - 力扣(LeetCode)

2.1 算法原理

正难则反 + 多源 BFS

  1. 将边界上的 1 进行入队操作
  2. 以边界上的 1 为起点, 进行多源 BFS, 将和其连通的其他的 1 进行标记.
  3. 最终, 返回内部未被标记的 1 的个数

 

2.2 算法代码

class Solution {public int numEnclaves(int[][] grid) {int m = grid.length, n = grid[0].length;int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};boolean[][] check = new boolean[m][n];Queue<int[]> q = new LinkedList<>();// 将边界上的 1 入队列for(int i = 0; i < m; i++) {if(grid[i][0] == 1) q.offer(new int[]{i, 0});if(grid[i][n - 1] == 1) q.offer(new int[]{i, n - 1});}for(int j = 0; j < n; j++) {if(grid[0][j] == 1) q.offer(new int[]{0, j});if(grid[m - 1][j] == 1) q.offer(new int[]{m - 1, j});}// 多源 BFS: 将和边界上连通的 1 进行标记while(!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];check[a][b] = true;for(int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !check[x][y]) {check[x][y] = true;q.offer(new int[]{x, y});}}}// 统计内部不连通的 1 的个数int ret = 0;for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) if(grid[i][j] == 1 && !check[i][j]) ret++;}return ret;}
}

3. 地图中的最高点

. - 力扣(LeetCode)

3.1 算法原理

  1. 由于任意相邻的格子高度差 至多 为 1, 所以应以水域位置为起点(水域位置固定高度为 0), 进行多源 BFS
  2. 将水域位置加入队列, 一层一层往外扩展.
  3. 每扩展到一个位置, 这个位置上的高度, 应为上个位置的高度 +1(求最高高度, 要求高度差不超过 1)

3.2 算法代码

class Solution {public int[][] highestPeak(int[][] isWater) {int m = isWater.length, n = isWater[0].length;int[][] height = new int[m][n];for(int i = 0; i < m; i++) Arrays.fill(height[i], -1);Queue<int[]> q = new LinkedList<>();for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(isWater[i][j] == 1) {height[i][j] = 0;q.offer(new int[]{i, j});}}}int[] dx = {1, -1, 0, 0};int[] dy = {0, 0 ,1, -1};while(!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];for(int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && height[x][y] == -1) {height[x][y] = height[a][b] + 1;q.offer(new int[]{x, y});}}}return height;}
}

4. 地图分析

. - 力扣(LeetCode)

4.1 算法原理

  1. 依旧是 正难则反 + BFS

  2. 创建一个 dist 数值, 将陆地位置初始化为 0 

  3. 以陆地位置为起点, 向外扩展, 扩展到的海洋位置的值是原来位置的值的基础上 +1(dist[x][y] = dist[a][b] + 1)

  4. dist 数组中的最大值, 就是海洋距离陆地的最远位置

4.2 算法代码

class Solution {public int maxDistance(int[][] grid) {int m = grid.length, n = grid[0].length;int[][] dist = new int[m][n];Queue<int[]> q = new LinkedList<>();for(int i = 0; i < m; i++) Arrays.fill(dist[i], -1);// 将陆地在 dist 中的位置初始化为 0// 并入队boolean sea = false;boolean ground = false;for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] == 1) {dist[i][j] = 0;q.offer(new int[]{i, j});}if(grid[i][j] == 0) sea = true;if(grid[i][j] == 1) ground =true;}}if(!sea || !ground) return -1;int[] dx = {1, -1, 0, 0};int[] dy = {0 ,0 , 1, -1};int ret = 0;while(!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];for(int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) {dist[x][y] = dist[a][b] + 1;q.offer(new int[]{x, y});ret = Math.max(ret, dist[x][y]);}}}return ret;}
}

END

相关文章:

BFS 算法专题(四):多源 BFS

目录 1. 01 矩阵 1.1 算法原理 1.2 算法代码 2. 飞地的数量 2.1 算法原理 2.2 算法代码 3. 地图中的最高点 3.1 算法原理 3.2 算法代码 4. 地图分析 4.1 算法原理 4.2 算法代码 1. 01 矩阵 . - 力扣&#xff08;LeetCode&#xff09; 1.1 算法原理 采用 BFS 正难…...

基于Spring Boot+Vue的养老院管理系统【原创】

一.系统开发工具与环境搭建 1.系统设计开发工具 后端使用Java编程语言的Spring boot框架 项目架构&#xff1a;B/S架构 运行环境&#xff1a;win10/win11、jdk17 前端&#xff1a; 技术&#xff1a;框架Vue.js&#xff1b;UI库&#xff1a;ElementUI&#xff1b; 开发工具&…...

Linux screen和cscope工具使用总结

1 minicom使用 1.1 minicom配置 第一次启动时&#xff1a; 如果输入sudo minicom提示错误&#xff0c;则需&#xff1a; sudo minicom -s 启动 出现配置菜单&#xff1a;选serial port setup 进入串口配置 输入A配置串口驱动为/dev/ttyUSB0 输入E配置速率为115200 8N1 输入F将 …...

深度学习面试八股汇总

按序发布&#xff1a; 深度学习——优化算法、激活函数、归一化、正则化 进入 深度学习——权重初始化、评估指标、梯度消失和梯度爆炸 进入 深度学习——前向传播与反向传播、神经网络&#xff08;前馈神经网络与反馈神经网络&#xff09;、常见算法 进入 深度学习——卷积神…...

微服务架构面试内容整理-API 网关-Gateway

Spring Cloud Gateway 是一个用于构建 API 网关的框架,它为微服务架构提供了灵活的路由和过滤功能。作为 Spring Cloud 生态的一部分,Gateway 提供了易于使用的 API 和强大的功能,适合用于现代微服务架构中的请求管理和服务交互。以下是 Spring Cloud Gateway 的主要特点、工…...

22.04Ubuntu---ROS2使用rclcpp编写节点C++

节点需要存在于功能包当中&#xff0c;功能包需要存在于工作空间当中。 所以我们要想创建节点&#xff0c;就要先创建一个工作空间&#xff0c;再创建功能包。 第一步&#xff1a;创建工作空间 mkdir -p chapt2_ws/src/ 第二步&#xff1a;创建example_cpp功能包&#xff0c…...

XML 现实案例:深入解析与应用

XML 现实案例:深入解析与应用 XML(可扩展标记语言)自1998年成为W3C推荐标准以来,一直是数据交换和存储的重要工具。它是一种用于标记电子文件的结构化语言,使得数据不仅人类可读,而且机器可处理。本文将探讨XML在现实世界中的应用案例,展示其如何在不同领域中发挥作用。…...

Spring源码(十二):Spring MVC之Spring Boot

本篇将详细讨论Spring Boot 的启动/加载、处理请求的具体流程。我们先从一个简单的Spring Boot项目日志开始分析&#xff08;这里假设读者已经仔细阅读完了前面的文章&#xff0c;且对Spring源码有一定深度的了解&#xff0c;否则会看得一脸懵逼&#xff09;。 本文为2024重置…...

Kafka 之事务消息

前言&#xff1a; 在分布式消息系统中&#xff0c;事务消息也是一个热门课题&#xff0c;在项目的实际业务场景中&#xff0c;如果用到事务消息的场景也不少见&#xff0c;那 Kafka 作为一个高性能的分布式消息中间件&#xff0c;同样也支持事务消息&#xff0c;本篇我们将对 …...

小菜家教平台(四):基于SpringBoot+Vue打造一站式学习管理系统

前言 昨天配置完了过滤器&#xff0c;权限检验&#xff0c;基本的SpringSecurity功能已经配置的差不多了&#xff0c;今天继续开发&#xff0c;明天可能会暂停一天整理一下需求&#xff0c;然后就进行CRUD了。 今日进度 补充SpringSecurity异常处理和全局异常处理器 详细操作…...

解决 Vue3、Vite 和 TypeScript 开发环境下跨域的问题,实现前后端数据传递

引言 本文介绍如何在开发环境下解决 Vite 前端&#xff08;端口 3000&#xff09;和后端&#xff08;端口 80&#xff09;之间的跨域问题&#xff1a; 在开发环境中&#xff0c;前端使用的 Vite 端口与后端端口不一致&#xff0c;会产生跨域错误提示&#xff1a; Access to X…...

量化交易系统开发-实时行情自动化交易-3.3.数据采集流程

19年创业做过一年的量化交易但没有成功&#xff0c;作为交易系统的开发人员积累了一些经验&#xff0c;最近想重新研究交易系统&#xff0c;一边整理一边写出来一些思考供大家参考&#xff0c;也希望跟做量化的朋友有更多的交流和合作。 接下来说说数据采集流程&#xff0c;后…...

探索PyAV:Python中的多媒体处理利器

文章目录 探索PyAV&#xff1a;Python中的多媒体处理利器第一部分&#xff1a;背景介绍第二部分&#xff1a;PyAV是什么&#xff1f;第三部分&#xff1a;如何安装PyAV&#xff1f;第四部分&#xff1a;简单的库函数使用方法1. 打开文件2. 查看流3. 遍历帧4. 编码帧5. 关闭输出…...

SpringBoot源码解析(三):启动开始阶段

SpringBoot源码系列文章 SpringBoot源码解析(一)&#xff1a;SpringApplication构造方法 SpringBoot源码解析(二)&#xff1a;引导上下文DefaultBootstrapContext SpringBoot源码解析(三)&#xff1a;启动开始阶段 目录 前言一、入口二、SpringApplicationRunListener1、作用…...

C# const与readonly关键字的区别

在C#中&#xff0c;readonly关键字用于定义在对象创建后不能更改的字段。它可以与常量(const)有些相似&#xff0c;但也有显著不同。以下是readonly关键字的一些关键点&#xff1a; 定义与用法&#xff1a; readonly字段可以在类的构造函数中初始化&#xff0c;而const字段必须…...

【数据分享】1901-2023年我国省市县镇四级的逐年降水数据(免费获取/Shp/Excel格式)

之前我们分享过1901-2023年1km分辨率逐月降水栅格数据和Shp和Excel格式的省市县四级逐月降水数据&#xff0c;原始的逐月降水栅格数据来源于彭守璋学者在国家青藏高原科学数据中心平台上分享的数据&#xff01;基于逐月数据我们采用求年累计值的方法得到逐年降水栅格数据&#…...

hhdb数据库介绍(9-4)

访问安全 权限体系 计算节点有两类用户&#xff0c;一类是计算节点数据库用户&#xff0c;用于操作数据&#xff0c;执行SELECT&#xff0c;UPDATE&#xff0c;DELETE&#xff0c;INSERT等SQL语句。另一类是关系集群数据库可视化管理平台用户&#xff0c;用于管理配置信息。此…...

苍穹外卖的分层所用到的技术以及工具+jwt令牌流程图(jwt验证)

分层用到的技术以及工具: jwt令牌流程图:...

Python——数列1/2,2/3,3/4,···,n/(n+1)···的一般项为Xn=n/(n+1),当n—>∞时,判断数列{Xn}是否收敛

没注释的源代码 from sympy import * n symbols(n) s n/(n1) print(数列的极限为&#xff1a;,limit(s,n,oo))...

css:还是语法

emmet的使用 emmet是一个插件&#xff0c;Emmet 是 Zen Coding 的升级版&#xff0c;由 Zen Coding 的原作者进行开发&#xff0c;可以快速的编写 HTML、CSS 以及实现其他的功能。很多文本编辑器都支持&#xff0c;我们只是学会使用它&#xff1a; 生成html结构 <!-- emme…...

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

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

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...