leetcode 542. 01 矩阵

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

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

示例 2:
输入: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 <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1.
mat 中至少有一个 0

思路:
可以采用广度遍历的方式来做,先把所有为 0 的元素进队列,然后依次计算出其临近的元素的距离,依次直到把矩阵中所有的元素的距离都计算完。

class Solution:
    def __init__(self):
        self.INT_MAX = 100000

    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        res = [[self.INT_MAX for j in range(cols)] for i in range(rows)]
        visited = [[0 for j in range(cols)] for i in range(rows)]
        ss = []
        for i in range(rows):
            for j in range(cols):
                if mat[i][j] == 0:
                    res[i][j] = 0
                    visited[i][j] = 1
                    ss.append((i, j))
        while len(ss) > 0:
            r, c = ss.pop(0)
            if r>0 and visited[r-1][c] == 0:
                ss.append((r-1, c))
                visited[r-1][c] = 1
                res[r-1][c] = min(res[r-1][c], res[r][c]+1)
            if r+1<rows and visited[r+1][c] == 0:
                ss.append((r+1, c))
                visited[r+1][c] = 1
                res[r+1][c] = min(res[r+1][c], res[r][c]+1)
            if c>0 and visited[r][c-1] == 0:
                ss.append((r, c-1))
                visited[r][c-1] = 1
                res[r][c-1] = min(res[r][c-1], res[r][c]+1)
            if c+1<cols and visited[r][c+1] == 0:
                ss.append((r, c+1))
                visited[r][c+1] = 1
                res[r][c+1] = min(res[r][c+1], res[r][c]+1)
        return res

方法二,采用动态规划来做
在这里插入图片描述

class Solution:
    def __init__(self):
        self.INT_MAX = 100000

    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        res = [[self.INT_MAX for j in range(cols)] for i in range(rows)]
        visited = [[0 for j in range(cols)] for i in range(rows)]
        ss = []
        for i in range(rows):
            for j in range(cols):
                if mat[i][j] == 0:
                    res[i][j] = 0
        ### from 左上
        for i in range(rows):
            for j in range(cols):
                if i-1>=0:
                    res[i][j] = min(res[i-1][j]+1, res[i][j])
                if j-1>=0:
                    res[i][j] = min(res[i][j-1]+1, res[i][j])
        ### from 右上
        for i in range(rows):
            for j in range(cols-1, -1, -1):
                if i-1>=0:
                    res[i][j] = min(res[i-1][j]+1, res[i][j])
                if j+1<cols:
                    res[i][j] = min(res[i][j+1]+1, res[i][j])
        
        ## from 左下
        for i in range(rows-1, -1, -1):
            for j in range(cols):
                if i+1<rows:
                    res[i][j] = min(res[i+1][j]+1, res[i][j])
                if j-1>=0:
                    res[i][j] = min(res[i][j-1]+1, res[i][j]) 
        
        ## from 右下
        for i in range(rows-1, -1, -1):
            for j in range(cols-1, -1, -1):
                if i+1<rows:
                    res[i][j] = min(res[i+1][j]+1, res[i][j])
                if j+1<cols:
                    res[i][j] = min(res[i][j+1]+1, res[i][j])
        return res

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

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

相关文章

7个有用的Prompt参数

ChatGPT和Midjournal使得生成式人工智能的应用程序激增。当涉及到生成式AI时&#xff0c;"prompt"通常指的是作为输入给模型的初始提示或指示。它是一个短语、问题、句子或段落&#xff0c;用来引导模型生成相关的响应或文本。 在使用生成式AI模型时&#xff0c;提供…

C++ 数据类型

使用编程语言进行编程时&#xff0c;需要用到各种变量来存储各种信息。变量保留的是它所存储的值的内存位置。这意味着&#xff0c;当您创建一个变量时&#xff0c;就会在内存中保留一些空间。 您可能需要存储各种数据类型&#xff08;比如字符型、宽字符型、整型、浮点型、双…

Unity3D+Hololens2+MRTK开发

最近项目要用Hololens2开发&#xff0c;公司新买了几套Hololens2设备&#xff0c;边学习边研究下吧。开始也是网上搜教程&#xff0c;但是问题还挺多的&#xff0c;大部分人的设置都不太对&#xff0c;有的是版本问题&#xff0c;走了好多弯路。现在就从零开始学习下Hololens2吧…

Spring【AOP】

AOP-面向切面编程 AOP&#xff1a;面向切面编程&#xff0c;通过预编译方式和运行期动态代理实现程序功能的统一维护的一种技术。 SpringAop中&#xff0c;通过Advice定义横切逻辑&#xff0c;并支持5种类型的Advice&#xff1a; 导入依赖 <dependency><groupId>…

解决git每次提交都需要输入用户密码

一、背景 在github上贴上了服务器ssh的公钥后&#xff0c;在服务器上推送代码仍旧提示需要输入git的账号和密码。 二、原因 这是因为此时的仓库是http协议下载的&#xff0c;此时的链接并不是通过ssh的&#xff0c;因此在推送代码时&#xff0c;会提示输入git的账号和密码。…

二叉树的右视图

给定一个二叉树的 根节点 root&#xff0c;想象自己站在它的右侧&#xff0c;按照从顶部到底部的顺序&#xff0c;返回从右侧所能看到的节点值。 示例 1: 输入: [1,2,3,null,5,null,4] 输出: [1,3,4] 示例 2: 输入: [1,null,3] 输出: [1,3] 示例 3: 输入: [] 输出: [] 代…

ifconfig不是eth0(eth1/2/3/4其他网卡)的解决办法

1. 编辑你网卡的配置文件 /etc/sysconfig/network-scripts/ifcfg-eth0&#xff0c;更改eth0中HWADDR 更改为eth1网卡的信息&#xff08;这里是16位的mac地址&#xff09; 2. 编辑配置文件 vi /etc/udev/rules.d/70-persistent-net.rules 打开该文件&#xff0c;这时你会发现&…

【基于 GitLab 的 CI/CD 实践】02、gitlab-runner 实践

目录 一、gitlab-runner 简介 1.1 要求 1.2 特点 二、GitLab Runner 安装 2.1 使用 GItLab 官方仓库安装 2.2 使用 deb/rpm 软件包 2.3 在容器中运行 GitLab Runner 三、GitLab Runner 注册 3.1 GitLabRunner 类型 3.2 获取 runner token 获取 shared 类型 runner t…

Redis双写一致性?

双写一致性&#xff1a;当修改了数据库的数据也要同时更新缓存的数据&#xff0c;缓存和数据库的数据要保持一致。 Redis作为缓存&#xff0c;mysql的数据如何与redis进行同步呢&#xff1f;&#xff08;双写一致性&#xff09; 1.我们当时做排行榜业务时&#xff0c;把历史榜…

RabbitMQ 同样的操作一次成功一次失败

RabbitMQ 是一个功能强大的消息队列系统&#xff0c;广泛应用于分布式系统中。然而&#xff0c;我遇到这样的情况&#xff1a;执行同样的操作&#xff0c;一次成功&#xff0c;一次失败。在本篇博文中&#xff0c;我将探讨这个问题的原因&#xff0c;并提供解决方法。 我是在表…

分布式定时任务组件:XXL-JOB

一、GitHub源码地址 https://github.com/xuxueli/xxl-job 二、部署文档 参考&#xff1a;https://blog.csdn.net/qq798867485/article/details/131415408 三、初始化数据库SQL 1、xxl_job_user XxlJob-用户管理 2、xxl_job_group XxlJob-执行器管理 3、xxl…

AI炒股:用Claude来分析A股2023年中报业绩预告

Claude是和ChatGPT类似的AI大模型&#xff0c;据测试 AI 的水平能力接近 GPT-4&#xff0c;支持高达 100K token 的上下文。Claude只需要到官方网站注册账号后就可以直接免费使用。不过&#xff0c;目前智能美国和英国的 IP 可以注册和使用。 Claude支持上传文档功能&#xff…

基于单片机的蓝牙音乐喷泉的设计与实现

功能介绍 以51单片机作为主控系统&#xff1b;通过HM-18蓝牙音频模块进行无线传输&#xff1b; 通过LM386功放模块对音频信号进行放大&#xff1b;手机端可以直接控制音频播放&#xff0c;并且最远距离可达20米&#xff1b;手机端可以进行任意音乐切换&#xff0c;播报、暂停&a…

Sql构建

Sql构建 SQL 构建对象介绍 之前通过注解开发时&#xff0c;相关 SQL 语句都是直接拼写的&#xff0c;一些关键字写起来比较麻烦、而且容易出错 MyBatis 提供了 org.apache.ibatis.jdbc.SQL 功能类&#xff0c;专门用于构建 SQL 语句 sql拼接测试&#xff1a; public class …

ROS:nodelet

目录 一、前言二、概念三、作用四、使用演示4.1案例简介4.2nodelet 基本使用语法4.3内置案例调用 五、nodelet实现5.1需求5.2流程5.3准备5.4创建插件类并注册插件5.5构建插件库5.6使插件可用于ROS工具链5.6.1配置xml5.6.2导出插件 5.7执行 一、前言 ROS通信是基于Node(节点)的…

SpringCloud学习路线(4)—— Nacos注册中心

一、认识和安装Nacos &#xff08;一&#xff09;概念&#xff1a; Nacos是Alibaba的产品&#xff0c;现在是SpringCloud中的一个组件&#xff0c;相较于Eureka功能更加丰富。 &#xff08;二&#xff09;下载地址&#xff1a; https://github.com/alibaba/nacos/releases &am…

UTM 4.3 发布:在 macOS 上优雅的使用 QEMU 虚拟化 Windows、Linux 和 macOS

UTM 4.3 发布&#xff1a;在 macOS 上优雅的使用 QEMU 虚拟化 Windows、Linux 和 macOS 在 iOS 中虚拟化 Windows、Linux 和 Unix 请访问原文链接&#xff1a;https://sysin.org/blog/utm-4/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xf…

活动页服务端渲染探索

目标 通过采用在服务端渲染激励页的方式&#xff0c;降低页面加载白屏时间&#xff0c;从而提升激励 H5 渲染体验。 架构设计 前端服务框架调研选型 只对比分析以下两种方案&#xff1a; Vue3 Nuxt3 WebpackNext.js React Node.js ’Nuxt3Next.js介绍Nuxt是一个基于Vu…

navicate_windows_14

1.新建文本文档2.输入如下内容 echo off set dnInfo set dn2ShellFolder set rpHKEY_CURRENT_USER\Software\Classes\CLSID :: reg delete HKEY_CURRENT_USER\Software\PremiumSoft\NavicatPremium\Registration14XCS /f %针对<strong><font color"#FF0000"…

文心一言 VS 讯飞星火 VS chatgpt (62)-- 算法导论6.5 1题

文心一言 VS 讯飞星火 VS chatgpt &#xff08;62&#xff09;-- 算法导论6.5 1题 一、试说明 HEAP-EXTRACT-MAX在堆A(15&#xff0c;13&#xff0c;9&#xff0c;5&#xff0c;12&#xff0c;8&#xff0c;7&#xff0c;4&#xff0c;0&#xff0c;6&#xff0c;2&#xff0c…
最新文章