当前位置: 首页 > 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/** # 设置权…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...