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 ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。 输入:mat [[0,0,0],[0,1,0],[0,0,0]] 输出:[[0,0,0],[0,1,0],[0,0,0]] 输入…...
怎么绘制简爱思维导图?用这个工具绘制很简单
怎么绘制简爱思维导图?绘制思维导图是一项非常有用的技能,有助于梳理思路、整理知识、更好地理解和记忆信息。因此,无论你是学生、教师、工程师、项目经理或者只是想要更好地组织自己的想法,学会绘制思维导图都是非常有益的。下面…...
EC200U-CN学习(三)
EC200U系列内置丰富的网络协议,集成多个工业标准接口,并支持多种驱动和软件功能(适用于Windows 7/8/8.1/10、Linux和Android等操作系统下的USB驱动),极大地拓展了其在M2M领域的应用范围,如POS、POC、ETC、共…...
【windows】连接共享打印机提示:0x0000011B
【问题现象】 添加共享打印机的时候, 提示错误:0x0000011B。 【解决方法】 按winr键,在运行输入regedit 然后在注册表中找到路径: 计算机\HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Print 打开后,在右侧…...
基于“RWEQ+”集成技术在土壤风蚀模拟与风蚀模数估算、变化归因分析中的实践应用及SCI论文撰写
【查看原文】基于“RWEQ”集成技术在土壤风蚀模拟与风蚀模数估算、变化归因分析中的实践应用及SCI论文撰写 土壤风蚀是一个全球性的环境问题。中国是世界上受土壤风蚀危害最严重的国家之一,土壤风蚀是中国干旱、半干旱及部分湿润地区土地荒漠化的首要过程。中国风…...
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解析服务配置文件,systemd为ubuntu下system and service配置目录 step 1——修改resolved.conf参数 管理员权限打开 /systemd/resolved.conf sudo nano /etc/systemd/resolved.conf修改如下: # 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 接口时,如何正确工作在非阻塞模式下? 3. TOE 使能及使用注意事项 4. TOE 模式下使用 socket 接口时的注意事项 1. 为什么UDP接收或发送会丢包? 用户态应用程序在接收 UDP 数据时࿰…...
spring拦截器 与统一格式
目录 前言模拟拦截器拦截器的实现原理什么是动态代理? 什么是静态代理静态代理与动态代理的区别两种常用的动态代理方式基于接口的动态代理基于类的动态代理 JDK Proxy 与 CGlib的区别 其他 统⼀访问前缀添加统⼀异常处理统⼀数据返回格式 前言 之前博客讲述了 , 关于SpringA…...
leetcode 122. 买卖股票的最佳时机 II
2023.7.29 把整体利润拆分成每天的利润,将股票值想象成一个折线图,将所有上升的值相加即可。 代码: class Solution { public:int maxProfit(vector<int>& prices) {int ans 0;for(int i1; i<prices.size(); i){if(prices[i]-…...
代理模式:控制访问的设计模式
代理模式:控制访问的设计模式 什么是代理模式? 代理模式是一种常见的设计模式,它允许通过代理对象来控制对真实对象的访问。代理模式的主要目的是在不改变原始对象的情况下,提供额外的功能或控制访问。 为什么要使用代理模式&a…...
2020/7/30
Educational Codeforces Round 143 (Rated for Div. 2)\C_Tea_Tasting.cpp //题意:有n种茶,n个人,第i种茶有 a[i]的量,第i个人一次能喝 b[i], 第i个人从第i种茶开始往前喝,求每个人最多能喝多少茶。 //思路ÿ…...
图形编辑器开发:是否要像 Figma 一样上 wasm
大家好,我是前端西瓜哥。 wasm 拿来做 Web 端的图形编辑器貌似是不错的选择。 因为图形处理会有相当多无法利用到 WebGL GPU 加速的 CPU 密集的计算。比如对一条复杂贝塞尔曲线进行三角化,对多个图形进行复杂图形的布尔运算。 图形编辑器性能天花板 F…...
Linux学成之路(基础篇0(二十三)MySQL服务(主从MySQL服务和读写分离——补充)
目录 一、MySQL Replication概述 优点 异步复制(Asynchronous repication) 全同步复制(Fully synchronous replication) 半同步复制(Semisynchronous replication) 三、MySQL支持的复制 四、部署主从…...
spring启动流程 (6完结) springmvc启动流程
SpringMVC的启动入口在SpringServletContainerInitializer类,它是ServletContainerInitializer实现类(Servlet3.0新特性)。在实现方法中使用WebApplicationInitializer创建ApplicationContext、创建注册DispatcherServlet、初始化ApplicationContext等。 SpringMVC…...
设计模式-中介者模式在Java中使用示例-客户信息管理
场景 欲开发客户信息管理窗口界面,界面组件之间存在较为复杂的交互关系:如果删除一个客户, 要在客户列表(List)中删掉对应的项,客户选择组合框(ComboBox)中客户名称也将减少一个; 如果增加一个客户信息,…...
14443-1-doc
介绍 ISO/IEC 14443 是描述 ISO/IEC 7810 中定义的身份证参数以及此类卡在国际交换中的使用的一系列国际标准之一。 ISO/IEC 14443 的这一部分描述了感应卡的物理特性。 ISO/IEC 14443 的这一部分并不排除在卡上纳入其他标准技术,例如资料性附录 A 中引用的技术。非…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
