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

LeetCode 542. 01 Matrix【多源BFS】中等

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:

输入:mat = [[0,0,0],[0,1,0],[0,0,0]]
输出:[[0,0,0],[0,1,0],[0,0,0]]

示例 2:

输入:mat = [[0,0,0],[0,1,0],[1,1,1]]
输出:[[0,0,0],[0,1,0],[1,2,1]]

提示:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 10^4
  • 1 <= m * n <= 10^4
  • mat[i][j] is either 0 or 1.
  • mat 中至少有一个 0

本题和「1162.地图分析」 一样!那道题理解为需要找到每个  0 0 0 最近的  1 1 1 ,而今天这道题是找每个  1 1 1 最近的  0 0 0

解法 多源BFS

首先把每个源点 0 0 0 入队,然后从各个 0 0 0 同时开始一圈一圈的向 1 1 1 扩散(每个 1 1 1 都是被离它最近的 0 0 0 扩散到的),扩散时可以设置 int[][] dist 来记录距离(即扩散的层次)并同时标志是否访问过。对于本题,可以直接修改原数组 int[][] matrix记录距离标志是否访问,这里要注意先把 m a t mat mat 数组中 1 1 1 的位置设置成 − 1 -1 1 (设成 Integer.MAX_VALUE m × n , m + n m \times n,\ m + n m×n, m+n 都行,只要是个无效的距离值来标志这个位置的 1 1 1 没有被访问过就行)

class Solution {
public:vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {int m = mat.size(), n = mat[0].size();int MAX_VALUE = m + n;queue<pair<int, int>> q;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (mat[i][j] == 0) q.push({i, j});else mat[i][j] = MAX_VALUE;}}int d[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};while (!q.empty()) {auto [x, y] = q.front(); q.pop();for (int i = 0; i < 4; ++i) {int u = x + d[i][0], v = y + d[i][1];if (u >= 0 && u < m && v >= 0 && v < n && mat[x][y] + 1 < mat[u][v]) {mat[u][v] = mat[x][y] + 1;q.push({u, v});}}}return mat;}
};

复杂度分析:

  • 时间复杂度: O ( m n ) O(mn) O(mn)
  • 空间复杂度:虽然我们是直接修改原输入数组来存储结果,但最差的情况下即全都是 0 0 0 时,需要把 m ∗ n m * n mn 0 0 0 都入队,因此空间复杂度是 O ( m n ) O(mn) O(mn)

相关文章:

LeetCode 542. 01 Matrix【多源BFS】中等

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

使用open cv进行角度测量

使用open cv进行角度测量 用了一点初中数学的知识&#xff0c;准确度&#xff0c;跟鼠标点的准不准有关系&#xff0c;话不多说直接上代码 import cv2 import mathpath "test.jpg" img cv2.imread(path) pointsList []def mousePoint(event, x, y, flags, param…...

java 线程池实现多线程处理list数据

newFixedThreadPool线程池实现多线程 List<PackageAgreementEntity> entityList new CopyOnWriteArrayList<>();//多线程 10个线程//int threadNum 10;int listSize 300;List<List<PackageAgreementDto>> splitData Lists.partition(packageAgre…...

Centos安装Docker

Centos安装 Docker 从 2017 年 3 月开始 docker 在原来的基础上分为两个分支版本: Docker CE 和 Docker EE。 Docker CE 即社区免费版&#xff0c;Docker EE 即企业版&#xff0c;强调安全&#xff0c;但需付费使用。 本文介绍 Docker CE 的安装使用。 移除旧的版本&#x…...

Unity启动项目无反应的解决

文章首发见博客&#xff1a;https://mwhls.top/4803.html。 无图/格式错误/后续更新请见首发页。 更多更新请到mwhls.top查看 欢迎留言提问或批评建议&#xff0c;私信不回。 摘要&#xff1a;通过退还并重新载入许可证以解决Unity项目启动无反应问题。 场景 Unity Hub启动项目…...

2.3 opensbi: riscv: opensbi源码解析

文章目录 3. sbi_init()函数4. init_coldboot()函数4.1 sbi_scratch_init()函数4.2 sbi_domain_init()函数4.3 sbi_scratch_alloc_offset()函数4.4 sbi_hsm_init()函数4.5 sbi_platform_early_init()函数3. sbi_init()函数 函数位置:lib/sbi/sbi_init.c函数参数:scratch为每个…...

点破ResNet残差网络的精髓

卷积神经网络在实际训练过程中&#xff0c;不可避免会遇到一个问题&#xff1a;随着网络层数的增加&#xff0c;模型会发生退化。    换句话说&#xff0c;并不是网络层数越多越好&#xff0c;为什么会这样&#xff1f; 不是说网络越深&#xff0c;提取的特征越多&#xff…...

Ubuntu服务器service版本初始化

下载 下载路径 官网&#xff1a;https://cn.ubuntu.com/ 下载路径&#xff1a;https://cn.ubuntu.com/download 服务器&#xff1a;https://cn.ubuntu.com/download/server/step1 点击下载&#xff08;22.04.3&#xff09;&#xff1a;https://cn.ubuntu.com/download/server…...

re学习(33)攻防世界-secret-galaxy-300(脑洞题)

下载压缩包&#xff1a; 下载链接&#xff1a;https://adworld.xctf.org.cn/challenges/list 参考文章&#xff1a;攻防世界逆向高手题之secret-galaxy-300_沐一 林的博客-CSDN博客 发现这只是三个同一类型文件的三个不同版本而已&#xff0c;一个windows32位exe&#xff0…...

Mybatis Plus中使用LambdaQueryWrapper进行分页以及模糊查询对比传统XML方式进行分页

传统的XML分页以及模糊查询操作 传统的XML方式只能使用limit以及offset进行分页&#xff0c;通过判断name和bindState是否为空&#xff0c;不为空则拼接条件。 List<SanitationCompanyStaff> getSanitationStaffInfo(Param("name") String name,Param("bi…...

vue中push和resolve的区别

import { useRouter } from vue-router;const routeuseRouter()route.push({path:/test,query:{name:1}})import { useRouter } from vue-router;const routeuseRouter()const urlroute.resolve({path:/test,query:{name:1}})window.open(url.href)比较上述代码会发现,resolve能…...

详解RFC 3550文档-1

1. 介绍 rfc 3550描述了实时传输协议RTP。RTP提供端到端的网络传输功能,适用于通过组播或单播网络服务传输实时数据(如音频、视频或仿真数据)的应用。 TP本身不提供任何机制来确保及时交付或提供其他服务质量保证,而是依赖于较低层的服务来完成这些工作。它不保证传输或防止…...

Go 与 Rust

目录 1. Go 与 Rust 1. Go 与 Rust 一位挺 Rust 的网友说道: “我也为这个选择烦恼了很久。最终 Rust 胜出了。首先, 我感觉 Rust 更接近于以前 Pascal 时代的东西, 你可以控制一切; 其次, 如果 wasm 和相关技术大爆发, Rust 将是一个更安全的选择; 然后, 我们已经有了 Python…...

Android Studio实现读取本地相册文件并展示

目录 原文链接效果 代码activity_main.xmlMainActivity 原文链接 效果 代码 activity_main.xml 需要有一个按钮和image来展示图片 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas.android.com/apk…...

python的全局解释锁(GIL)

一、介绍 全局解释锁&#xff08;Global Interpreter Lock&#xff0c;GIL&#xff09;是在某些编程语言的解释器中使用的一种机制。在Python中&#xff0c;GIL是为了保证解释器线程安全而引入的。 GIL的作用是在解释器的执行过程中&#xff0c;确保同一时间只有一个线程可以…...

小程序swiper一个轮播显示一个半内容且实现无缝滚动

效果图&#xff1a; wxml&#xff08;无缝滚动&#xff1a;circular"true"&#xff09;&#xff1a; <!--components/tool_version/tool_version.wxml--> <view class"tool-version"><swiper class"tool-version-swiper" circul…...

【自然语言处理】关系抽取 —— SimpleRE 讲解

SimpleRE 论文信息 标题:An Embarrassingly Simple Model for Dialogue Relation Extraction 作者:Fuzhao Xue 期刊:ICASSP 2022 发布时间与更新时间:2020.12.27 2022.01.25 主题:自然语言处理、关系抽取、对话场景、BERT arXiv:[2012.13873] An Embarrassingly Simple M…...

【O2O领域】Axure外卖订餐骑手端APP原型图,外卖众包配送原型设计图

作品概况 页面数量&#xff1a;共 110 页 兼容软件&#xff1a;Axure RP 9/10&#xff0c;不支持低版本 应用领域&#xff1a;外卖配送、生鲜配送 作品申明&#xff1a;页面内容仅用于功能演示&#xff0c;无实际功能 作品特色 本品为外卖订餐骑手端APP原型设计图&#x…...

DataGridView keydown事件无法在C#中工作

原因&#xff1a;单元格内编辑文本时,DataGridView keydown事件不起作用。每当单元格处于编辑模式时,其托管控件就会接收KeyDown事件而不是DataGridView包含它的父级.这就是为什么当单元格未处于编辑模式时(即使它被选中),键盘快捷键正常工作,因为DataGridView控件本身会收到Ke…...

【ElasticSearch】一键安装ElasticSearch与Kibana以及解决遇到的问题

目录 一、安装ES 二、安装Kibana 三、遇到的问题 一、安装ES 按顺序复制即可 docker network create es-net # 创建网络 docker pull images:7.12.1 # 拉取镜像 mkdir -p /root/es/data # 创建数据卷 mkdir -p /root/es/plugins # 创建数据卷 chmod 777 /root/es/** # 设置权…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

​​企业大模型服务合规指南:深度解析备案与登记制度​​

伴随AI技术的爆炸式发展&#xff0c;尤其是大模型&#xff08;LLM&#xff09;在各行各业的深度应用和整合&#xff0c;企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者&#xff0c;还是积极拥抱AI转型的传统企业&#xff0c;在面向公众…...

STM32标准库-ADC数模转换器

文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”&#xff1a;输入模块&#xff08;GPIO、温度、V_REFINT&#xff09;1.4.2 信号 “调度站”&#xff1a;多路开关1.4.3 信号 “加工厂”&#xff1a;ADC 转换器&#xff08;规则组 注入…...

高效的后台管理系统——可进行二次开发

随着互联网技术的迅猛发展&#xff0c;企业的数字化管理变得愈加重要。后台管理系统作为数据存储与业务管理的核心&#xff0c;成为了现代企业不可或缺的一部分。今天我们要介绍的是一款名为 若依后台管理框架 的系统&#xff0c;它不仅支持跨平台应用&#xff0c;还能提供丰富…...