当前位置: 首页 > 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 中引用的技术。非…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

【Java_EE】Spring MVC

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

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...