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

优选算法系列(8.多源BFS)

简介·:

01 矩阵(medium):

题目链接:542. 01 矩阵 - 力扣(LeetCode)

算法:

对于求的最终结果,我们有两种方式:
  • 第⼀种方式:从每⼀个 1 开始,然后通过层序遍历找到离它最近的 0 这⼀种方式,我们会以所有的 1 起点,来⼀次层序遍历,势必会遍历到很多重复的点。并且如果矩阵中只有⼀个 0 的话,每⼀次层序遍历都要遍历很多层,时间复杂度较高·。
  • 换⼀种方式:从 0 开始层序遍历,并且记录遍历的层数。当第⼀次碰到 1 的时候,当前的层数就是这个 1 0 的最短距离。 这⼀种方式,我们在遍历的时候标记⼀下处理过的 1 ,能够做到只用遍历整个矩阵⼀次,就能得到最终结果。
但是,这里有⼀个问题, 0 是有很多个的,我们怎么才能保证遇到的 1 距离这⼀个 0 是最近的呢?
其实很简单,我们可以先把所有的 0 都放在队列中,把它们当成⼀个整体,每次把当前队列里面的所有元素向外扩展⼀次。
第一层:
第二层:
第三层:
C++:

 java:

飞地的数量(medium) 

题目链接:1020. 飞地的数量 - 力扣(LeetCode)

算法:

正难则反:
  • 从边上的 1 开始搜索,把与边上 1 相连的联通区域全部标记⼀下;
  • 然后再遍历⼀遍矩阵,看看哪些位置的 1 没有被标记即可
标记的时候,可以⽤「多源 bfs 」解决。
和 算法系列6 中的 被围绕的区域(medium) 差不多,那里使用的是单源BFS
C++:

Java:

地图中的最高点(medium)

题目链接:1765. 地图中的最高点 - 力扣(LeetCode)


算法;

01矩阵的变型题,直接用多源 bfs 解决即可。

地图分析(medium):

题目链接:1162. 地图分析 - 力扣(LeetCode)


算法:

01矩阵的变型题,直接⽤多源 bfs 解决即可
http://www.xdnf.cn/news/317485.html

相关文章:

  • Vue3响应式:effect作用域
  • linux命令>/dev/null 2>1的含义
  • 【北京迅为】iTOP-4412精英版使用手册-第七章 Android 4.0/Linux源码编译
  • 在 Vue 2 中使用 qrcode 库生成二维码
  • Python 识别图片上标点位置
  • CSDN文章都是VIP
  • Ubuntu 使用dotfiles个性化配置模板
  • 使用 Apache POI 生成包含文本和图片的 Word 文档
  • 【MCP】从0到1实现一个MCP Client
  • 【Python类(Class)完全指南】面向对象编程入门
  • 阿里云服务器-centos部署定时同步数据库数据-dbswitch
  • 【Django】中间件
  • 软件工程(三):模块的内聚模型
  • 如何在大型项目中解决 VsCode 语言服务器崩溃的问题
  • 政务浏览器 一站式首页功能配置说明
  • 极狐GitLab 命名空间的类型有哪些?
  • css animation 动画属性
  • 华为昇腾910B通过vllm部署InternVL3-8B教程
  • 大模型系列(五)--- GPT3: Language Models are Few-Shot Learners
  • IPFS集群部署
  • Linux/AndroidOS中进程间的通信线程间的同步 - 信号量
  • Java游戏服务器开发流水账(1)游戏服务器的架构浅析
  • Wireshark抓账号密码
  • 一文走进GpuGeek | conda常用命令
  • Prompt(提示词)工程师,“跟AI聊天”
  • Java版ERP管理系统源码(springboot+VUE+Uniapp)
  • FID和IS的区别
  • STM32裸机开发问题汇总
  • (1-1)Java的JDK、JRE、JVM三者间的关系
  • 淘宝按图搜索商品(拍立淘)爬虫实战指南