C++ | Leetcode C++题解之第542题01矩阵

题目:

题解:

class Solution {
public:vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();// 初始化动态规划的数组,所有的距离值都设置为一个很大的数vector<vector<int>> dist(m, vector<int>(n, INT_MAX / 2));// 如果 (i, j) 的元素为 0,那么距离为 0for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (matrix[i][j] == 0) {dist[i][j] = 0;}}}// 只有 水平向左移动 和 竖直向上移动,注意动态规划的计算顺序for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {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 (int i = m - 1; i >= 0; --i) {for (int j = 0; j < n; ++j) {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 (int i = 0; i < m; ++i) {for (int j = n - 1; j >= 0; --j) {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 (int i = m - 1; i >= 0; --i) {for (int j = n - 1; j >= 0; --j) {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;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

分布式——BASE理论

简单来说&#xff1a; BASE&#xff08;Basically Available、Soft state、Eventual consistency&#xff09;是基于CAP理论逐步演化而来的&#xff0c;核心思想是即便不能达到强一致性&#xff08;Strong consistency&#xff09;&#xff0c;也可以根据应用特点采用适当的方…

安卓智能指针sp、wp、RefBase浅析

目录 前言一、RefBase1.1 引用计数机制1.2 设计目的1.3 主要方法1.4 如何使用1.5 小结 二、sp和wp2.1 引用计数机制2.2 设计目的2.3 主要方法2.3.1 sp2.3.2 wp 2.4 如何使用2.5 小结 四、参考链接 前言 安卓底层binder中&#xff0c;为什么 IInterface要继承自RefBase &#x…

k8s 上如何跑 Dolphins 模型

接着上一篇的介绍&#xff0c;这一篇就来跑跑 Dolphins 模型&#xff0c;本篇会记录&#xff0c;跑模型常见的阬点。 1 在 k8s 上创建 pod 将外部数据挂载在 pod 里&#xff0c;并申请 gpu 资源。同时修改代码里对应的引入数据的路径 # dolphins.yaml apiVersion: v1 kind: …

CentOS 7 更换软件仓库

CentOS 7 于2024年6月30日停止维护&#xff0c;官方仓库已经没有软件了&#xff0c;想要继续使用 &#xff0c;需要更换软件仓库&#xff0c;这里更换到阿里云的软件仓库 https://developer.aliyun.com/mirror/ 查看目前可用的软件数量 yum repolist 更换软件仓库&#xff1a…

初学者指南:用例图——开启您的软件工程之旅

目录 背景&#xff1a; 基本组成&#xff1a; 关联&#xff08;Assciation&#xff09;&#xff1a; 包含&#xff08;Include&#xff09;&#xff1a; 扩展&#xff08;Extend&#xff09;&#xff1a; 泛化&#xff08;Inheritance&#xff09;&#xff1a; 完整银行…

单位正交矢量的参数化,用于特征矢量对厄尔米特矩阵对角化使用

​ 首先α β 在0-pi/2内&#xff0c;这样就可以取值0-1&#xff0c;满足了单位化的要求 每个向量的模由α和β定义&#xff0c;αβ定义模的时候只限制在0–pi/2&#xff0c;由画图可知不可正交 为了验证矩阵 U 3 \boldsymbol{U}_3 U3​ 的第一列和第二列是否正交&#xff…

Spring Security 框架篇-深入了解 Spring Security 的授权核心功能(RBAC 权限模型、自定义异常处理器、校验权限方法)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 权限系统 1.1 引入 1.2 RBAC 权限模型 1.3 数据库设计 2.0 Spring Security 核心功能-授权 2.1 思路分析 2.2 编写 SQL 语句 2.3 将用户权限进行封装 2.4 获取用户…

使用 API 和离线库查询 IP 地址方法详解

目录 一、IP 地址查询能获取哪些信息1.地理位置信息2.网络信息3.网络类型 二、IP 地址查询方法&#xff0c;附代码1.在线查询 IP 地址方法2.使用 API 进行 IP 地址查询3.使用离线库进行 IP 地址查询 互联网监管部门要求公开 IP 归属地&#xff0c;引起了很大热度&#xff0c;但…

微服务day02

教学文档&#xff1a; 黑马教学文档 Docker Docker的安装 镜像和容器 命令解读 常见命令 案例 查看DockerHub&#xff0c;拉取Nginx镜像&#xff0c;创建并运行容器 搜索Nginx镜像&#xff1a;在 www.hub.docker.com 网站进行查询 拉取镜像&#xff1a; docker pull ngin…

一个小程序如何对接多个收款账户?

背景 我又来了&#xff0c;之前对接过网约巴士系统 网约巴士旅游专线平台搭建历程&#xff0c;运营了两年多了。在运营中完善、在完善中学习&#xff0c;一直是不变的真理。有一句话说得好&#xff1a;先做一个垃圾、用起来再说。 今天又需要升级了&#xff0c;需求是&#…

基于航片的玉米异常情况识别赛题正在报名中 | CCF BDCI进行时

一年一度的行业盛事2024 CCF大数据与计算智能大赛&#xff08;简称2024 CCF BDCI&#xff09;又在激烈进行中啦 多个赛题等你挑战&#xff0c;还没有报名的伙伴们抓紧时间咯&#xff0c;叫上你伙伴练起来吧&#xff01; 2024 CCF大数据与计算智能大赛 CCF大数据与计算智能大…

面试题:Spring(一)

1. Spring框架中bean是单例么&#xff1f; Service Scope("singleton") public class UserServiceImpl implements UserService { }singleton : bean在每个Spring IOC容器中只有一个实例。prototype&#xff1a;一个bean的定义可以有多个实例。 2. Spring框架中的…

Android View事件分发

目录 1.什么是View事件分发&#xff1f; 2.事件的类型 3.事件的发生 4.事件分发的方法 4.1 dispatchTouchEvent() 4.2 onTouchEvent() 4.3 onInterceptTouchEvent() 5.滑动冲突 5.1 外部拦截法 5.2内部拦截法 6.onTouch的执行高于onClick 7. onTouch()和onTouchEve…

uniapp 实现瀑布流

效果演示 组件下载 瀑布流布局-waterfall - DCloud 插件市场

6.qsqlquerymodel源码分析

目录 继承关系入口浅析qsqlquery刷新数据 扩展列或者移除列以及取别名读取数据与增减行读取数据 下一章节&#xff1a;如何使用qsqlquerymodel 与 qtableview实现自定义表格 继承关系 qsqlquerymodel 继承与qabstracttablemodel 入口 负责填充数据 void QSqlQueryModel::s…

Vue3中使用LogicFlow实现简单流程图

实现结果 实现功能&#xff1a; 拖拽创建节点自定义节点/边自定义快捷键人员选择弹窗右侧动态配置组件配置项获取/回显必填项验证历史记录&#xff08;撤销/恢复&#xff09; 自定义节点与拖拽创建节点 拖拽节点面板node-panel.vue <template><div class"node-…

Devops业务价值流:软件研发最佳实践

在当今快速迭代的软件开发环境中&#xff0c;DevOps业务价值流已成为推动软件研发高效与质量并重的关键实践。软件研发阶段作为产品生命周期的核心环节&#xff0c;其每一步都承载着将创意转化为现实的重要使命。在历经需求澄清的精准定位、架构设计的宏观规划以及项目初始化的…

wireshark工具使用

复制数据 1.右键展开整帧数据 2.复制“所有可见项目” mark标记数据 标记&#xff1a; 跳转&#xff1a; 保存成文件&#xff1a; 文件–>导出特定分组—>Marked packets only

管理 Elasticsearch 变得更容易了,非常容易!

作者&#xff1a;来自 Elastic Ken Exner Elasticsearch 用户&#xff0c;我们听到了你的心声。管理 Elasticsearch 有时会变得很复杂&#xff0c;面临的挑战包括性能调整、问题检测和资源优化。我们一直致力于简化你的体验。今天&#xff0c;我们宣布了自收购 Opster 以来的一…

深度洞察| 超6亿银发精准流量,40+泛银发群体参与消费三大变化

作者 | NewAgingPro团队 前言 9月24日&#xff0c;AgeClub成立银发流量及场景联盟&#xff08;简称&#xff1a;AgeMCN&#xff09;&#xff0c;助力银发经济高质量发展。 10月11日&#xff0c;AgeClub发布《2024银发流量全景洞察报告》&#xff0c;探索银发流量发展新模式…