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

LintCode第974题-求矩阵各节点的最短路径(以0为标准)

news 来源：原创 2025/9/6 0:29:00

描述

给定一个由0和1组成的矩阵，求每个单元格最近的0的距离。
两个相邻细胞之间的距离是1。

给定矩阵的元素数不超过10,000。
在给定的矩阵中至少有一个0。
单元格在四个方向上相邻:上，下，左和右。

样例

例1:

输入:
[[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0]]
输出:
[[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0]]

例2:

输入:
[[0,1,0,1,1],[1,1,0,0,1],[0,0,0,1,0],[1,0,1,1,1],[1,0,0,0,1]]
输出:
[[0,1,0,1,2],[1,1,0,0,1],[0,0,0,1,0],[1,0,1,1,1],[1,0,0,0,1]]

本题主要考察广度优先搜索

如需更快更简洁的算法请跳至思路2

思路1:

思路1虽然也是广度优先搜索算法但是是单源的广度优先搜索算法即逐个继续遍历扩展其周围的元素

外层循环为每一层,内层循环为每一层的当前输入值

然后通过两个变量 path来记录路径的长度队列来记录为未满足为0的位置索引每次判断但凡队列的点相邻但凡没有一个符合条件就先让path+1

然后记录所有不符合的点直至循环出相邻有0的点因为题目已经告知给定的矩阵至少有一个0

这就是每一个元素的遍历

最后将所有元素都这样执行一遍就可以得到每一个单元距离0的距离

即简要理解为针对每个 1 向外找最近 0

代码如下:

import java.util.*;

public class Solution {

/**

* @param matrix: a 0-1 matrix

* @return: return a matrix

public int[][] updateMatrix(int[][] matrix) {

int m = matrix.length;

int n = matrix[0].length;

int[][] pathMatrix = new int[m][n]; // 最终结果矩阵

int path; // 当前单元格的路径

Queue<int[]> integerQueue = new LinkedList<>(); // 存坐标的队列

// 遍历每个单元格

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (matrix[i][j] == 0) {

pathMatrix[i][j] = 0;

} else {

// BFS 查找最近的 0

boolean[][] visited = new boolean[m][n];

integerQueue.clear();

integerQueue.offer(new int[]{i, j});

visited[i][j] = true;

path = 0;

boolean found = false;

while (!integerQueue.isEmpty() && !found) {

int size = integerQueue.size();

path++; // 每扩展一层，路径 +1

for (int q = 0; q < size; q++) {

int[] pos = integerQueue.poll();

int x = pos[0];

int y = pos[1];

int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}}; // 上下左右

for (int[] dir : dirs) {

int nx = x + dir[0];

int ny = y + dir[1];

if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {

if (matrix[nx][ny] == 0) {

pathMatrix[i][j] = path;

found = true;

break;

} else {

integerQueue.offer(new int[]{nx, ny});

visited[nx][ny] = true;

}

if (found) break;

}

return pathMatrix;

}

时间复杂度为:O(m × n)^2

思路2:多源广度优先算法

同时从多个起点出发进行 BFS，也就是说：
不是一个一个来，而是全部起点一起“向外一层层扩散”

即所有 0 一起扩散访问一次就是最短路径无冗余访问即类似于同步水波扩散

需要注意的是

m代表的是行数

n代表的是列数

代码如下:

public class Solution {

public int[][] updateMatrix(int[][] matrix) {

int m = matrix.length;

int n = matrix[0].length;

int[][] pathMatrix = new int[m][n];

boolean[][] visited = new boolean[m][n];

Queue<int[]> integerQueue = new LinkedList<>();

//注意这里用LinkList 因为效率高入队出队都是O(1) 而且LinkList实现了Deque,Deque又继承了队列,所以Queue可以直接用其实现类 LinkList.

// 将所有为0的点入队，作为BFS的起点

for (int y = 0; y < m; y++) {

for (int x = 0; x < n; x++) {

if (matrix[y][x] == 0) {

integerQueue.offer(new int[]{y, x});

visited[y][x] = true;

}

// 上下左右

int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

while (!integerQueue.isEmpty()) {

int[] point = integerQueue.poll();

int y = point[0], x = point[1];

for (int[] dir : directions) {

int newY = y + dir[0];

int newX = x + dir[1];

if (newY >= 0 && newY < m && newX >= 0 && newX < n && !visited[newY][newX]) {

pathMatrix[newY][newX] = pathMatrix[y][x] + 1;

visited[newY][newX] = true;

integerQueue.offer(new int[]{newY, newX});

}

return pathMatrix;

}

LintCode第974题-求矩阵各节点的最短路径(以0为标准)

描述给定一个由0和1组成的矩阵，求每个单元格最近的0的距离。两个相邻细胞之间的距离是1。给定矩阵的元素数不超过10,000。在给定的矩阵中至少有一个0。单元格在四个方向上相邻:上，下，左和右。样例例1: 输入: [[0,0,0],[0,0,0],[0…...

编程日记 2025/9/6 0:29:00

吴恩达深度学习复盘(6)神经网络的矢量化原理

矢量化基础是线性运算，这里先简单复习一下。线性基本运算基本没什么，大量使用的有点乘和叉乘。基本例子 1. 矩阵的基本概念 - 矩阵可以看作是一个块或者二维数组，这是对矩阵的一个在计算机计算的直观描述。 2. 向量的点积（内积…...

编程日记 2025/9/1 9:42:24

ISIS多区域配置

一、什么是ISIS多区域 ISIS（Intermediate System to Intermediate System）多区域是指网络被划分为多个逻辑区域（Areas），不同区域之间通过特定的ISIS路由器（Level-1-2）进行路由交互。多区域设计提…...

编程日记 2025/9/1 9:42:14

The emulator process for AVD xxx has terminated

问题描述离线环境下部署Android虚拟机，启动时报错The emulator process for AVD xxx has terminated，其中xxx为虚拟机名称。解决过程可先在C:\Users\admin\AppData\Local\Google\AndroidStudio2024.3\log目录下找到idea.log文件，其中记录…...

编程日记 2025/9/4 15:22:16

Haskell语言的区块链扩展性

Haskell语言的区块链扩展性研究引言区块链技术近年来在金融、供应链、物联网等多个领域取得了显著的进展。作为一种分布式账本技术，区块链的核心在于其去中心化、不可篡改和透明性。然而，随着应用的不断深入，区块链面临着可扩展性、性能、…...

编程日记 2025/9/1 9:41:48

第11/100节：三点估算

第11/100节：三点估算三、完成某信息系统集成项目中的一个最基本的工作单元 A 所需的时间，乐观的估计需 8 天，悲观的估计需 38天，最可能的估计需 20 天，按照三点估算方法进行估算，项目的工期应该为&#xf…...

编程日记 2025/9/3 18:26:16

Tourists

一道圆方树恶心题，*3200，不知道为什么不评黑。这道题很容易直接想到圆方树：因为两个操作如果在树上，都需要树链剖分线段树维护。而将这么一个普通图转化为一棵树，也就只有圆方树这种形式了。于是就可以综合使用圆…...

编程日记 2025/9/1 9:41:29

【动态规划】深入动态规划：连续子结构的算法剖析

文章目录前言例题一、最大子数组和二、环形子数组的最大和三、乘积最大子数组四、乘积为正数的最长子数组五、等差数列划分六、最长湍流子数组七、单词拆分八、环绕字符串中唯一的子字符串结语前言什么是是动态规划连续子数组、子串系列算法问题? 连续子数组问题通常聚焦…...

编程日记 2025/9/1 1:10:45

结肠镜3D视频数据集-C3VD论文中文版

文章目录标题作者摘要一、介绍1.1. 相关工作1.1.1. 内镜重建数据集1.1.2. 注册真实和虚拟内窥镜图像1.1.3. 2D-3D注册1.2. 贡献二、方法2.1. 幻影模型生产2.2. 数据采集2.3. 注册流程概述2.3.1. 数据预处理2.3.2. 目标深度估计2.3.3. 渲染深度帧2.3.4. 边缘损失和优化 2.4. 模…...

编程日记 2025/9/1 9:41:05

封装自己的api签名sdk

api平台接口调用，需要通过签名去核对是不是有效的用户，，一般会给两个key，acceeKey 和 secretKey,第一个相当于用户名，第二个相当于密钥，，，前端通过一定的算法，&#xff0…...

编程日记 2025/9/1 9:40:57

ASP.NET Core Web API 中 HTTP状态码的分类及对应的返回方法

文章目录前言一、HTTP状态码分类及常用方法二、具体返回方法示例1） 2xx 成功类2）4xx 客户端错误3）5xx 服务器错误4）其他特殊状态码三、高级返回方式1）使用 IActionResult 与 ActionResult<T>2）统一…...

编程日记 2025/9/3 0:37:10

函数和模式化——python

一、模块和包将一段代码保存为应该扩展名为.py 的文件，该文件就是模块。Python中的模块分为三种，分别为：内置模块、第三方模块和自定义模块。内置模块和第三方模块又称为库内置模块，有 python 解释器自带，不用单独安…...

编程日记 2025/9/5 2:01:26

LeetCode 1817 查找用户活跃分钟数

深入剖析 LeetCode 用户活跃分钟数统计问题一、题目详情给定用户在 LeetCode 的操作日志，日志以二维整数数组logs表示，其中每个logs[i][IDi, timei]，意味着 ID 为IDi的用户在timei分钟时执行了某个操作。多个用户能够同时执行操作&#x…...

编程日记 2025/9/4 14:29:49

matlab从pytorch中导入LeNet-5网络框架

文章目录一、Pytorch的LeNet-5网络准备二、保存用于导入matlab的model三、导入matlab四、用matlab训练这个导入的网络这里演示从pytorch的LeNet-5网络导入到matlab中进行训练用。一、Pytorch的LeNet-5网络准备根据LeNet-5的结构图，我们可以写如下结构 import…...

编程日记 2025/9/3 22:24:42

网络：华为HCIA学习笔记：ICMP协议

ICMP（Internet Control Message Protocol）Internet控制消息协议前言ICMPICMP重定向ICMP差错监测ICMP错误报告ICMP数据包格式ICMP消息类型和编码类型ICMP应用-PingICMP应用-Tracert 总结前言 Internet控制消息协议ICMP (Internet Control Message Prot…...

编程日记 2025/9/5 12:58:10

Visio | 将(.vsdx)导出为更清楚/高质量的图片(.png) | 在Word里面的visio图

此时大家在用Visio画完图直接复制到word里面后，如果后期需要重新保存高清图片，但是此时图片在word，是不是很多人会选择直接crtlA截图复制，这样出来的图又不清晰又小，完全不符合你导的审美，接下来跟着我&…...

编程日记 2025/9/4 2:59:37

算法设计学习8

实验目的及要求： 通过深入学习树（Tree）和二叉树（Binary Tree）这两种重要的数据结构，掌握它们的基本概念、性质和操作，提高对树形结构的理解和应用能力。通过本实验，学生将深化对树和…...

编程日记 2025/9/1 9:39:39

Dive into Deep Learning - 2.4. Calculus (微积分)

Dive into Deep Learning - 2.4. Calculus {微积分} 1. Derivatives and Differentiation (导数和微分)1.1. Visualization Utilities 2. Chain Rule (链式法则)3. DiscussionReferences 2.4. Calculus https://d2l.ai/chapter_preliminaries/calculus.html For a long time, …...

编程日记 2025/9/1 9:39:27

kotlin中const 和val的区别

在 Kotlin 中，const 和 val 都是用来声明常量的，但它们的使用场景和功能有所不同： 1. val: val 用于声明只读变量，也就是不可修改的变量（类似于 Java 中的 final 变量）。它可以是任何类型，包括…...

编程日记 2025/9/1 9:39:06

Webpack中loader的作用。

文章目录前言1. 处理样式文件2. 处理 JavaScript 文件3. 处理其他文件总结前言在 Webpack 中，Loader 是用于对模块的源代码进行转换的工具，它能够将不同类型的文件（如 CSS、图片、字体、TypeScript 等）转换为有效的 JavaScrip…...

编程日记 2025/9/1 9:38:58

C++ 极简常用内容

C 极简常用内容 1. 类与对象定义：封装数据（成员变量）和行为（成员函数）的自定义类型。 Demo： class Car { public:string brand;void drive() { cout << brand << " is moving." …...

编程日记 2025/9/2 14:50:40

如何在windows 环境、且没有显卡的情况下用python跑通从ModelScope下载的大模型的调用

文章目录背景介绍源代码：安装调试过程1.设置第三方镜像源2.预先安装：3.在python中创建代码：4.最终修改程序,将device_map从“cuda”改成“auto”，大模型调用1.5B（1___5B)的5.最终跑出结果解释：示例&#x…...

编程日记 2025/9/1 9:38:30

MINIQMT学习课程Day10

开始获取股票数据课程的学习： 获取qmt账号的持仓情况后，我们进入下一步，如何获得当前账号的委托状况还是之前的步骤，打开qmt，选择独立交易， 之后使用pycharm，编写py文件导入包&#xff1a…...

编程日记 2025/9/1 9:38:18

如何彻底关闭Windows 10中的Xbox游戏栏

一、打工人的困扰：不速之客“Game Bar” 在日常工作中，许多使用Windows 10的用户常常被一个不起眼却频频打扰的系统功能困扰，那就是“Xbox游戏栏”（Game Bar）。当你正在专注处理紧急的Excel表格或准备PPT汇报&#xf…...

编程日记 2025/9/4 1:26:07

26考研资料分享考研资料合集百度网盘（仅供参考学习）

考研资料分享考研资料合集百度网盘（仅供参考学习） 通过网盘分享的文件：2026考研英语数学政治最新等3个文件链接1: https://pan.baidu.com/s/1JXBI9ROng4KAWHoaUHpkug?pwdjydb 提取码: jydb 链接2:https://pan.baidu.com/s/1a…...

编程日记 2025/9/1 9:37:48

59.基于ssm和vue学生考试成绩管理系统

目录 1.系统的受众说明 2.系统关键技术 2.1 java技术 2.2 MYSQL数据库 2.3 B/S结构 3.系统分析 3.1 可行性分析 3.1.1 技术可行性 3.1.2经济可行性 3.2 系统性能分析 3.3 系统功能分析 3.5系统流程分析 3.5.1登录流程 3.5.2注册流程 3.5.3添加信息流程 3.5.4删…...

编程日记 2025/9/1 9:37:37

常见的ETL工具分类整理

一、开源ETL工具 ‌Kettle（Pentaho Data Integration）--Spoon‌ 设计及架构：面向数据仓库建模的传统ETL工具。使用方式：C/S客户端模式，开发和生产环境需要独立部署，任务编写、调试、修改都在本地。底层架构…...

编程日记 2025/9/3 19:18:32

【leetcode100】数组中的第K个最大元素

1、题目描述给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。示例 1: 输入: [3,2,…...

编程日记 2025/9/2 8:22:28

markdown语法学习

三化markdown语法研究对象系统化全局化结构化markdown语法富文本字体样式*斜体*，主题样式#，表格样式||，代码块样式，待办样式- [ ]样式之间互相协作，互不冲突待办斜体加粗标题删除线 public class{ //代码块 …...

编程日记 2025/9/2 8:22:24

Linux_4

开始学习ssh工具在做开发的时候，肯定不止一台服务器，那么假设每台服务器都是Linux服务器，要在服务器上操作就需要登入终端，即Terminal。ssh的作用就是可以通过一个服务器登陆上其他的服务器。登陆到哪个服务器看到的就是哪个服务器的终端terminal。 ssh登陆 ssh user@…...

编程日记 2025/9/2 8:22:20

Netty——连接超时与断开重连

文章目录 1. 处理连接超时和断开重连的原因2. 处理连接超时和断开重连的方法2.1 处理连接超时2.1.1 步骤一：配置连接超时时间2.1.2 步骤二：监听连接结果 2.2 处理断开重连2.2.1 步骤一：监听连接断开事件2.2.2 步骤二：实现重连逻辑…...

编程日记 2025/9/5 0:09:53

linux 进程/线程设置核亲和性

1，线程绑定内核 #include <pthread.h> #include <stdio.h> #include <stdlib.h> // 定义一个函数，用于设置线程的CPU亲和性 void set_thread_affinity(pthread_t thread, int cpu_id) { cpu_set_t cpuset; int s; // 清空CPU集…...

编程日记 2025/9/5 0:09:56

前端页面鼠标移动监控（鼠标运动、鼠标监控）鼠标节流处理、throttle、限制触发频率（setTimeout、clearInterval）

文章目录使用lodashjs库手动实现节流（通过判断之前设定的定时器setTimeout是否存在） 使用lodashjs库 <!DOCTYPE html> <html lang"zh-CN"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Com…...

编程日记 2025/9/5 1:33:13

【MySQL基础-21】MySQL事务机制详解：原理、实现与最佳实践

在现代数据库系统中，事务机制是确保数据一致性和完整性的核心技术。MySQL作为最流行的开源关系型数据库之一，其事务实现机制对于开发者而言至关重要。本文将深入探讨MySQL的事务机制，包括核心概念、实现原理、隔离级别以及实际应用中的最佳实…...

编程日记 2025/9/2 8:22:03

Transformer+BO-SVM时间序列预测（Matlab）

TransformerBO-SVM时间序列预测（Matlab） 目录 TransformerBO-SVM时间序列预测（Matlab）效果一览基本介绍程序设计参考资料效果一览基本介绍普通的单变量时序已经用腻了，审稿人也看烦了，本期推出一期高创…...

编程日记 2025/9/3 23:00:21

Python循环控制语句

1. 循环类型概述 Python提供两种主要的循环结构： while循环 - 在条件为真时重复执行for循环 - 遍历序列中的元素 2. while循环基本语法 while 条件表达式:循环体代码示例 count 0 while count < 5:print(f"这是第{count1}次循环")count 13. f…...

编程日记 2025/9/2 8:21:54

4.4日西南竞篮，欧篮联，NBA，全扫盘

欧篮联扫盘 301奥林匹亚 vs 阿尔巴 （11.5），总分167.5：阿尔巴有伤病，点差11.5大，可能是接近比赛，总分较低，预测阿尔巴赢盘，总分低于167.5。 302埃菲斯 vs 贝红星 (-1.5)&a…...

编程日记 2025/9/4 9:44:48

面试可能会遇到的问题回答（嵌入式软件开发部分）

写在前面： 博主也是刚入社会的小牛马，如果下面有写的不好或者写错的地方欢迎大家指出~ 一、四大件基础知识 1、计算机组成原理 （1）简单介绍一下中断是什么。 ①回答： ②难度系数：★★ ③难点分析&…...

编程日记 2025/9/4 7:11:27

AI平台初步规划实现和想法

要实现一个类似Coze的工作流搭建引擎，可以结合SmartEngine作为后端工作流引擎，ReactFlow作为前端流程图渲染工具，以及Ant Design作为UI组件库。以下是实现的步骤和关键点： ### 1. 后端工作流引擎（SmartEngine&#xf…...

编程日记 2025/9/3 19:09:09

软件工程面试题（二十七）

1、j a v a 对象初始化顺序 1.类的初始化（initialization class & interface） 2.对象的创建（creation of new class instances）顺序：应为类的加载肯定是第一步的，所以类的初始化在前。大体的初始化顺序是：类初始化 -> 子类构造函数 -> 父类构造函数 -&g…...

编程日记 2025/9/5 6:57:38

CCF GESP C++编程六级认证真题 2025年3月

C 六级 2025 年 03 月题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 D B A B B B B A A A A A B C A 一、单选题第 1 题在面向对象编程中，类是一种重要的概念。下面关于类的描述中，不正确的是（ ）。 A. 类是一个抽象的概念&a…...

编程日记 2025/9/2 8:21:35

Cortex-M 上编写汇编函数

在 ARM Cortex-M 系列单片机中使用汇编语言编写函数时，需要特别注意寄存器的使用、栈管理、调用约定以及与 C 语言的兼容性。以下是关键注意事项和示例说明： 1. 遵循 AAPCS 调用约定 ARM 定义了 AAPCS（ARM Architecture Procedure Call Standard），规定了函数调用时寄存器…...

编程日记 2025/9/3 13:00:59

Spring 核心技术解析【纯干货版】- XXII：Spring 扫描效率提升模块 Spring-Context-Indexer 模块精讲

在 Spring 应用中，组件扫描（Component Scan） 是 Spring 容器启动时的关键任务之一。默认情况下，Spring 通过反射扫描整个类路径来找到所有 Component、Service、Repository 等注解的类，并将其注册为 Spring Bean。但…...

编程日记 2025/9/4 22:44:41

jetson AGX orin--ARM64 换源报错Packages 404 Not Found [IP: 2402:f000:1:400::2 443]

问题原因： ARM64结构不能使用X86结构的源，清华源不完全支持ARM64。使用下面这个源 sudo vim /etc/apt/sources.list 删掉原来的，改成这个 # ARM64 架构专用源 deb [archarm64] http://ports.ubuntu.com/ubuntu-ports focal main restrict…...

编程日记 2025/9/2 8:21:21

对备忘录模式的理解

对备忘录模式的理解一、场景1、题目【[来源](https://kamacoder.com/problempage.php?pid1095)】1.1 题目描述1.2 输入描述1.3 输出描述1.4 输入示例1.5 输出示例 2、理解需求二、不采用备忘录设计模式1、代码2、问题3、错误的备忘录模式三、采用备忘录设计模式1、代码1.1 …...

编程日记 2025/9/4 9:19:36

ngx_ssl_init

定义在 src\event\ngx_event_openssl.c ngx_int_t ngx_ssl_init(ngx_log_t *log) { #if OPENSSL_VERSION_NUMBER > 0x10100003Lif (OPENSSL_init_ssl(OPENSSL_INIT_LOAD_CONFIG, NULL) 0) {ngx_ssl_error(NGX_LOG_ALERT, log, 0, "OPENSSL_init_ssl() failed")…...

编程日记 2025/9/4 9:35:58

Roo Code（前身为 Roo Cline）一个 AI 驱动的自主编码代理

Roo Code（前身为 Roo Cline） Roo Code 是一个 AI 驱动的自主编码代理，它存在于您的编辑器中。它可以： 用自然语言沟通直接在您的工作区读写文件运行终端命令自动化浏览器操作与任何 OpenAI 兼容或自定义的 API/模型集成通过自定…...

编程日记 2025/9/5 13:23:29

每日一题洛谷P8649 [蓝桥杯 2017 省 B] k 倍区间c++

P8649 [蓝桥杯 2017 省 B] k 倍区间 - 洛谷 (luogu.com.cn) #include <iostream> #include <vector> using namespace std; #define int long long signed main() {int n, k;cin >> n >> k;vector<int> a(n 1);vector<int> sum(n 1);vec…...

编程日记 2025/9/2 8:21:04

CLion安装、配置及使用

目录 1 CLion是什么 2 CLion安装 3 系统环境变量配置 4 CLion配置 4.1 编辑器选择 4.2 编辑器配置 4.3 新建项目 5 总结 1 CLion是什么 CLion 是 JetBrains 推出的一款跨平台集成开发环境（IDE），专为 C 和 C 开发设计，支…...

编程日记 2025/9/4 20:24:42

UE5把动画导出为视频格式

UE5把动画导出为视频格式步骤一点击渲染视频或图片按钮旁边的三个圆点按钮步骤二点击渲染视频或图片按钮步骤三 1是修改输出视频的帧率格式 2输出视频的路径 3点击等待视频渲染完成以上是基本方法最新的输出视频方法请看这位大佬的视频...

编程日记 2025/9/2 8:20:55

相关文章：