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 m∗n 个 0 0 0 都入队,因此空间复杂度是 O ( m n ) O(mn) O(mn)
相关文章:

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

使用open cv进行角度测量
使用open cv进行角度测量 用了一点初中数学的知识,准确度,跟鼠标点的准不准有关系,话不多说直接上代码 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 即社区免费版,Docker EE 即企业版,强调安全,但需付费使用。 本文介绍 Docker CE 的安装使用。 移除旧的版本&#x…...
Unity启动项目无反应的解决
文章首发见博客:https://mwhls.top/4803.html。 无图/格式错误/后续更新请见首发页。 更多更新请到mwhls.top查看 欢迎留言提问或批评建议,私信不回。 摘要:通过退还并重新载入许可证以解决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残差网络的精髓
卷积神经网络在实际训练过程中,不可避免会遇到一个问题:随着网络层数的增加,模型会发生退化。 换句话说,并不是网络层数越多越好,为什么会这样? 不是说网络越深,提取的特征越多ÿ…...

Ubuntu服务器service版本初始化
下载 下载路径 官网:https://cn.ubuntu.com/ 下载路径:https://cn.ubuntu.com/download 服务器:https://cn.ubuntu.com/download/server/step1 点击下载(22.04.3):https://cn.ubuntu.com/download/server…...

re学习(33)攻防世界-secret-galaxy-300(脑洞题)
下载压缩包: 下载链接:https://adworld.xctf.org.cn/challenges/list 参考文章:攻防世界逆向高手题之secret-galaxy-300_沐一 林的博客-CSDN博客 发现这只是三个同一类型文件的三个不同版本而已,一个windows32位exe࿰…...

Mybatis Plus中使用LambdaQueryWrapper进行分页以及模糊查询对比传统XML方式进行分页
传统的XML分页以及模糊查询操作 传统的XML方式只能使用limit以及offset进行分页,通过判断name和bindState是否为空,不为空则拼接条件。 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)
一、介绍 全局解释锁(Global Interpreter Lock,GIL)是在某些编程语言的解释器中使用的一种机制。在Python中,GIL是为了保证解释器线程安全而引入的。 GIL的作用是在解释器的执行过程中,确保同一时间只有一个线程可以…...

小程序swiper一个轮播显示一个半内容且实现无缝滚动
效果图: wxml(无缝滚动:circular"true"): <!--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原型图,外卖众包配送原型设计图
作品概况 页面数量:共 110 页 兼容软件:Axure RP 9/10,不支持低版本 应用领域:外卖配送、生鲜配送 作品申明:页面内容仅用于功能演示,无实际功能 作品特色 本品为外卖订餐骑手端APP原型设计图&#x…...
DataGridView keydown事件无法在C#中工作
原因:单元格内编辑文本时,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 (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...

Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: 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(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)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 文件,或者在构建过程中仍然引用了旧的路…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
Bean 作用域有哪些?如何答出技术深度?
导语: Spring 面试绕不开 Bean 的作用域问题,这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开,结合典型面试题及实战场景,帮你厘清重点,打破模板式回答,…...

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