Python | Leetcode Python题解之第542题01矩阵

题目:

题解:

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])
        # 初始化动态规划的数组,所有的距离值都设置为一个很大的数
        dist = [[10**9] * n for _ in range(m)]
        # 如果 (i, j) 的元素为 0,那么距离为 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    dist[i][j] = 0
        # 只有 水平向左移动 和 竖直向上移动,注意动态规划的计算顺序
        for i in range(m):
            for j in range(n):
                if i - 1 >= 0:
                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)
                if j - 1 >= 0:
                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)
        # 只有 水平向左移动 和 竖直向下移动,注意动态规划的计算顺序
        for i in range(m - 1, -1, -1):
            for j in range(n):
                if i + 1 < m:
                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)
                if j - 1 >= 0:
                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)
        # 只有 水平向右移动 和 竖直向上移动,注意动态规划的计算顺序
        for i in range(m):
            for j in range(n - 1, -1, -1):
                if i - 1 >= 0:
                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)
                if j + 1 < n:
                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)
        # 只有 水平向右移动 和 竖直向下移动,注意动态规划的计算顺序
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if i + 1 < m:
                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)
                if j + 1 < n:
                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)
        return dist

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/910069.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

RabbitMQ 管理平台(控制中心)的介绍

文章目录 一、RabbitMQ 管理平台整体介绍二、Overview 总览三、Connections 连接四、Channels 通道五、Exchanges 交换机六、Queues 队列查看队列详细信息查看队列的消息内容 七、Admin 用户给用户分配虚拟主机 一、RabbitMQ 管理平台整体介绍 RabbitMQ 管理平台内有六个模块&…

【机器学习】聚类算法分类与探讨

&#x1f497;&#x1f497;&#x1f497;欢迎来到我的博客&#xff0c;你将找到有关如何使用技术解决问题的文章&#xff0c;也会找到某个技术的学习路线。无论你是何种职业&#xff0c;我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章&#xff0c;也欢…

易语言模拟真人动态生成鼠标滑动路径

一.简介 鼠标轨迹算法是一种模拟人类鼠标操作的程序&#xff0c;它能够模拟出自然而真实的鼠标移动路径。 鼠标轨迹算法的底层实现采用C/C语言&#xff0c;原因在于C/C提供了高性能的执行能力和直接访问操作系统底层资源的能力。 鼠标轨迹算法具有以下优势&#xff1a; 模拟…

Linux:防火墙和selinux对服务的影响

1-1selinux 1-1 SELinux是对程序、文件等权限设置依据的一个内核模块。由于启动网络服务的也是程序&#xff0c;因此刚好也 是能够控制网络服务能否访问系统资源的一道关卡。 1-2 SELinux是通过MAC的方式来控制管理进程&#xff0c;它控制的主体是进程&#xff0c;而目标则是…

华为eNSP:QinQ

一、什么是QinQ&#xff1f; QinQ是一种网络技术&#xff0c;全称为"Quantum Insertion"&#xff0c;也被称为"Q-in-Q"、"Double Tagging"或"VLAN stacking"。它是一种在现有的VLAN&#xff08;Virtual Local Area Network&#xff0…

运动控制 PID算法

文章目录 一、自动控制简介1.1 开环控制系统1.2 闭环控制系统1.3 电机速度闭环控制系统 二、PID算法2.1 比例2.1.1 静态误差 2.2 积分2.3 微分环节2.4 位置式PID2.5 增量式PID 一、自动控制简介 自动控制系统是使用自动控制装置对关键控制参数进行自动控制&#xff0c;使它在收…

Pytorch实现transformer语言模型

转载自&#xff1a;| 03_language_model/02_Transformer语言模型.ipynb | 从头训练Transformer语言模型 |Open In Colab | Transformer语言模型 本节训练一个 sequence-to-sequence 模型&#xff0c;使用pytorch的 nn.Transformer <https://pytorch.org/docs/master/nn.ht…

C语言例题练手(1)

前几篇博客的内容已经涉及了C语言的部分语法知识&#xff0c;我们可以尝试做一些编程题&#xff0c;或者换一种说法就是可以写出什么样的程序以此来解决一些问题。 题目来自牛客网https://www.nowcoder.com和C语言菜鸟教程C 语言教程 | 菜鸟教程 数值计算 【例1】带余除法计…

Spring AI 核心概念

SpringAI 核心概念 1. Models2. Prompts3. Prompt Templates4. Embeddings5. Tokens6. Structured Output7. Bringing Your Data & APIs to the AI Model7.1 Retrieval Augmented Generation7.2 Function Calling 1. Models AI 模型是用于处理和生成信息的算法&#xff0c…

http请求响应详解

http介绍 http协议&#xff1a; Http”协议称为是“超文本传输协议”&#xff08;HTTP-Hypertext transfer protocol&#xff09;。它定义了浏览器怎么向万维网服务器请求万维网文档&#xff0c;以及服务器怎么样把文档传送给浏览器。 https协议&#xff1a; 传统的HTTP协议…

直播系统搭建教程安装说明

需要安装的软件(宝塔【软件商店】中查找安装): 1.PHP7.0 ~ PHP7.3 需要安装的扩展:(宝塔【PHP管理】【安装扩展】中安装) *PDO PHP Extension * MBstring PHP Extension * CURL PHP Extension * Mylsqi PHP Extension * Redis PHP Extension * fileinfo PHP Extension …

redis7学习笔记

文章目录 1. 简介1.1 功能介绍1.1.1 分布式缓存1.1.2 内存存储和持久化(RDBAOF)1.1.3 高可用架构搭配1.1.4 缓存穿透、击穿、雪崩1.1.5 分布式锁1.1.6 队列 1.2 数据类型StringListHashSetZSetGEOHyperLogLogBitmapBitfieldStream 2. 命令2.1 通用命令copydeldumpexistsexpire …

51c~C语言~合集1

我自己的原文哦~ https://blog.51cto.com/whaosoft/12428240 一、C语言和C的区别 ​ C语言虽说经常和C在一起被大家提起&#xff0c;但可千万不要以为它们是一个东西。现在我们常用的C语言是C89标准&#xff0c;C是C99标准的。C89就是在1989年制定的标准&#xff0c;如今最新…

【论文解读】EdgeYOLO:一种边缘实时目标检测器(附论文地址)

论文地址&#xff1a;https://arxiv.org/pdf/2302.07483 这篇文章的标题是《EdgeYOLO: An Edge-Real-Time Object Detector》&#xff0c;由中国北京理工大学的Shihan Liu、Junlin Zha、Jian Sun、Zhuo Li和Gang Wang共同撰写。这篇论文提出了一个基于最新YOLO框架的高效、低复…

基于SSM的企业管理系统(源码+lw+调试+技术指导)

项目描述 临近学期结束&#xff0c;还是毕业设计&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。这里根据疫情当下&#xff0c;你想解决的问…

【MyBatis源码】CacheKey缓存键的原理分析

文章目录 Mybatis缓存设计缓存KEY的设计CacheKey类主体CacheKey组成CacheKey如何保证缓存key的唯一性 Mybatis缓存设计 MyBatis 每秒过滤众多数据库查询操作&#xff0c;这对 MyBatis 缓存键的设计提出了很高的要求。MyBatis缓存键要满足以下几点。 无碰撞&#xff1a;必须保证…

Mac M1 Docker创建Rocketmq集群并接入Springboot项目

文章目录 前言Docker创建rocketmq集群创建rocketmq目录创建docker-compose.yml新增broker.conf文件启动容器 Springboot 接入 rocketmq配置maven依赖修改appplication.yml新增消息生产者新增消费者测试发送消息 总结 前言 最近公司给配置了一台mac&#xff0c;正好有时间给装一…

pycharm小游戏贪吃蛇及pygame模块学习()

由于代码量大&#xff0c;会逐渐发布 一.pycharm学习 在PyCharm中使用Pygame插入音乐和图片时&#xff0c;有以下这些注意事项&#xff1a; 插入音乐&#xff1a; - 文件格式支持&#xff1a;Pygame常用的音乐格式如MP3、OGG等&#xff0c;但MP3可能需额外安装库&#xf…

使用Rust实现http/https正向代理

相关库的安装 利用vcpkg安装openssl库 vcpkg install openssl:x64-windows并设置openssl库位置的环境变量 $Env:OPENSSL_DIR"D:/vcpkg/packages/openssl_x64-windows/"安装openssl软件&#xff0c;因为需要利用openssl生成自签名证书 Cargo依赖 [dependencies] …

基于MATLAB的运动车辆跟踪检测系统

一、课题介绍 本设计为基于MATLAB的运动车辆跟踪检测系统。带有一个GUI界面&#xff0c;可以读取高速路车流视频&#xff0c;读取视频信息&#xff0c;并且统计每辆车经过左车道还是右车道&#xff0c;车速和平均速度检测&#xff0c;以及某一帧下的车流密度&#xff0c;以及最…