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

01 矩阵(力扣)多源广度优先搜索 JAVA

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

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

在这里插入图片描述

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

在这里插入图片描述

输入: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

解题思路:

1、相邻指的是上下左右四方向

2、与其以1为起点,不如以所有0为起点,这是个不错的逆向思维

3、所有0初始值为0,所有1初始值Integer.MAX_VALUE/2

4、前者值 + 1比后者值小即可更新后者值

代码:

class Solution {public int fx[] = {-1, 1, 0, 0};public int fy[] = {0, 0, -1, 1};//上下左右public int INF = Integer.MAX_VALUE / 2;public int[][] updateMatrix(int[][] mat) {int m = mat.length;int n = mat[0].length;Queue<int[]> qu = new LinkedList<>();for(int i = 0; i < m; i ++)for(int j = 0; j < n; j ++)if(mat[i][j] == 0) {qu.add(new int[] {i, j});}else mat[i][j] = INF;bfs(qu, mat, m, n);return mat;}public void bfs(Queue<int[]> qu, int[][] mat, int m, int n) {while(!qu.isEmpty()) {int xy[] = qu.poll();for(int i = 0;i < 4; i ++) {int fxx = xy[0] + fx[i];int fyy = xy[1] + fy[i];if(fxx >= 0 && fxx < m && fyy >= 0 && fyy < n && mat[xy[0]][xy[1]] + 1 < mat[fxx][fyy]) {mat[fxx][fyy] = mat[xy[0]][xy[1]] + 1;qu.add(new int[]{fxx, fyy});}}}}
}

在这里插入图片描述

相关文章:

01 矩阵(力扣)多源广度优先搜索 JAVA

给定一个由 0 和 1 组成的矩阵 mat &#xff0c;请输出一个大小相同的矩阵&#xff0c;其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。 输入&#xff1a;mat [[0,0,0],[0,1,0],[0,0,0]] 输出&#xff1a;[[0,0,0],[0,1,0],[0,0,0]] 输入…...

怎么绘制简爱思维导图?用这个工具绘制很简单

怎么绘制简爱思维导图&#xff1f;绘制思维导图是一项非常有用的技能&#xff0c;有助于梳理思路、整理知识、更好地理解和记忆信息。因此&#xff0c;无论你是学生、教师、工程师、项目经理或者只是想要更好地组织自己的想法&#xff0c;学会绘制思维导图都是非常有益的。下面…...

EC200U-CN学习(三)

EC200U系列内置丰富的网络协议&#xff0c;集成多个工业标准接口&#xff0c;并支持多种驱动和软件功能&#xff08;适用于Windows 7/8/8.1/10、Linux和Android等操作系统下的USB驱动&#xff09;&#xff0c;极大地拓展了其在M2M领域的应用范围&#xff0c;如POS、POC、ETC、共…...

【windows】连接共享打印机提示:0x0000011B

【问题现象】 添加共享打印机的时候&#xff0c; 提示错误&#xff1a;0x0000011B。 【解决方法】 按winr键&#xff0c;在运行输入regedit 然后在注册表中找到路径&#xff1a; 计算机\HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Print 打开后&#xff0c;在右侧…...

基于“RWEQ+”集成技术在土壤风蚀模拟与风蚀模数估算、变化归因分析中的实践应用及SCI论文撰写

【查看原文】基于“RWEQ”集成技术在土壤风蚀模拟与风蚀模数估算、变化归因分析中的实践应用及SCI论文撰写​ 土壤风蚀是一个全球性的环境问题。中国是世界上受土壤风蚀危害最严重的国家之一&#xff0c;土壤风蚀是中国干旱、半干旱及部分湿润地区土地荒漠化的首要过程。中国风…...

Flutter-基础Widget

Flutter页面-基础Widget 文章目录 Flutter页面-基础WidgetWidgetStateless WidgetStateful WidgetState生命周期 基础widget文本显示TextRichTextDefaultTextStyle 图片显示FlutterLogoIconImageIamge.assetImage.fileImage.networkImage.memory CircleAvatarFadeInImage 按钮R…...

【数据分析专栏之Python篇】二、Jupyer Notebook安装配置及基本使用

文章目录 前言一、Jupter Notebook是什么1.1 简介1.2 组成部分1.3 Jupyter Notebook的主要特点 二、为什么使用Jupyter Notebook?三、安装四、Jupyter Notebok配置4.1 基本配置4.2 配置开机自启与后台运行4.3 开启代码自动补全 五、两种键盘输入模式5.1 编辑模式5.2 命令模式5…...

ubuntu22.04 DNSSEC(加密DNS服务) configuration

/etx/systemd/resolved.conf是ubuntu下DNS解析服务配置文件&#xff0c;systemd为ubuntu下system and service配置目录 step 1——修改resolved.conf参数 管理员权限打开 /systemd/resolved.conf sudo nano /etc/systemd/resolved.conf修改如下&#xff1a; # This file i…...

Qt 第一讲

登录框设置 #include "zuoye.h" #include "ui_zuoye.h"Zuoye::Zuoye(QWidget *parent): QWidget(parent), ui(new Ui::Zuoye) {ui->setupUi(this);//界面this->resize(540,420); //设置尺寸this->setFixedSize(540,420);//固定尺寸this->setS…...

IDEA 使用 maven 搭建 spring mvc

1. 创建项目 1.1 创建成功之后配置 Spring MVC 1.2 勾选 Spring MVC 2.更改配置文件 2.1 更改web.xml配置 更改为 <servlet-mapping><servlet-name>dispatcher</servlet-name><url-pattern>/</url-pattern></servlet-mapping>2.2 dispat…...

Hi3536网络应用调优

目录 1. 为什么UDP接收或发送会丢包? 2. 使用 socket 接口时&#xff0c;如何正确工作在非阻塞模式下&#xff1f; 3. TOE 使能及使用注意事项 4. TOE 模式下使用 socket 接口时的注意事项 1. 为什么UDP接收或发送会丢包? 用户态应用程序在接收 UDP 数据时&#xff0…...

spring拦截器 与统一格式

目录 前言模拟拦截器拦截器的实现原理什么是动态代理? 什么是静态代理静态代理与动态代理的区别两种常用的动态代理方式基于接口的动态代理基于类的动态代理 JDK Proxy 与 CGlib的区别 其他 统⼀访问前缀添加统⼀异常处理统⼀数据返回格式 前言 之前博客讲述了 , 关于SpringA…...

leetcode 122. 买卖股票的最佳时机 II

2023.7.29 把整体利润拆分成每天的利润&#xff0c;将股票值想象成一个折线图&#xff0c;将所有上升的值相加即可。 代码&#xff1a; class Solution { public:int maxProfit(vector<int>& prices) {int ans 0;for(int i1; i<prices.size(); i){if(prices[i]-…...

代理模式:控制访问的设计模式

代理模式&#xff1a;控制访问的设计模式 什么是代理模式&#xff1f; 代理模式是一种常见的设计模式&#xff0c;它允许通过代理对象来控制对真实对象的访问。代理模式的主要目的是在不改变原始对象的情况下&#xff0c;提供额外的功能或控制访问。 为什么要使用代理模式&a…...

2020/7/30

Educational Codeforces Round 143 (Rated for Div. 2)\C_Tea_Tasting.cpp //题意&#xff1a;有n种茶&#xff0c;n个人&#xff0c;第i种茶有 a[i]的量&#xff0c;第i个人一次能喝 b[i], 第i个人从第i种茶开始往前喝&#xff0c;求每个人最多能喝多少茶。 //思路&#xff…...

图形编辑器开发:是否要像 Figma 一样上 wasm

大家好&#xff0c;我是前端西瓜哥。 wasm 拿来做 Web 端的图形编辑器貌似是不错的选择。 因为图形处理会有相当多无法利用到 WebGL GPU 加速的 CPU 密集的计算。比如对一条复杂贝塞尔曲线进行三角化&#xff0c;对多个图形进行复杂图形的布尔运算。 图形编辑器性能天花板 F…...

Linux学成之路(基础篇0(二十三)MySQL服务(主从MySQL服务和读写分离——补充)

目录 一、MySQL Replication概述 优点 异步复制&#xff08;Asynchronous repication&#xff09; 全同步复制&#xff08;Fully synchronous replication&#xff09; 半同步复制&#xff08;Semisynchronous replication&#xff09; 三、MySQL支持的复制 四、部署主从…...

spring启动流程 (6完结) springmvc启动流程

SpringMVC的启动入口在SpringServletContainerInitializer类&#xff0c;它是ServletContainerInitializer实现类(Servlet3.0新特性)。在实现方法中使用WebApplicationInitializer创建ApplicationContext、创建注册DispatcherServlet、初始化ApplicationContext等。 SpringMVC…...

设计模式-中介者模式在Java中使用示例-客户信息管理

场景 欲开发客户信息管理窗口界面&#xff0c;界面组件之间存在较为复杂的交互关系&#xff1a;如果删除一个客户&#xff0c; 要在客户列表(List)中删掉对应的项&#xff0c;客户选择组合框(ComboBox)中客户名称也将减少一个&#xff1b; 如果增加一个客户信息&#xff0c;…...

14443-1-doc

介绍 ISO/IEC 14443 是描述 ISO/IEC 7810 中定义的身份证参数以及此类卡在国际交换中的使用的一系列国际标准之一。 ISO/IEC 14443 的这一部分描述了感应卡的物理特性。 ISO/IEC 14443 的这一部分并不排除在卡上纳入其他标准技术&#xff0c;例如资料性附录 A 中引用的技术。非…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

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

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

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

【免费数据】2005-2019年我国272个地级市的旅游竞争力多指标数据(33个指标)

旅游业是一个城市的重要产业构成。旅游竞争力是一个城市竞争力的重要构成部分。一个城市的旅游竞争力反映了其在旅游市场竞争中的比较优势。 今日我们分享的是2005-2019年我国272个地级市的旅游竞争力多指标数据&#xff01;该数据集源自2025年4月发表于《地理学报》的论文成果…...

PH热榜 | 2025-06-08

1. Thiings 标语&#xff1a;一套超过1900个免费AI生成的3D图标集合 介绍&#xff1a;Thiings是一个不断扩展的免费AI生成3D图标库&#xff0c;目前已有超过1900个图标。你可以按照主题浏览&#xff0c;生成自己的图标&#xff0c;或者下载整个图标集。所有图标都可以在个人或…...