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

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;}
};

相关文章:

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

题目&#xff1a; 题解&#xff1a; class Solution { public:vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {int m matrix.size(), n matrix[0].size();// 初始化动态规划的数组&#xff0c;所有的距离值都设置为一个很大的…...

RabbitMQ 不公平分发介绍

RabbitMQ 是一个流行的开源消息代理软件&#xff0c;它实现了高级消息队列协议&#xff08;AMQP&#xff09;。在 RabbitMQ 中&#xff0c;消息分发策略对于系统的性能和负载均衡至关重要。默认情况下&#xff0c;RabbitMQ 使用公平分发&#xff08;Fair Dispatch&#xff09;策…...

测试实项中的偶必现难测bug--一键登录失败

问题描述:安卓和ios有出现部分一键登录失败的场景,由于场景比较极端,衍生了很多不好评估的情况。 产生原因分析: 目前有解决过多次这种行为的问题,每次的产生原因都有所不同,这边根据我个人测试和收集复现的情况列举一些我碰到的: 1、由于我们调用的是友盟的一键登录的…...

危!这些高危端口再不知道问题就大了

号主&#xff1a;老杨丨11年资深网络工程师&#xff0c;更多网工提升干货&#xff0c;请关注公众号&#xff1a;网络工程师俱乐部 下午好&#xff0c;我的网工朋友。 端口作为网络通信的基本单元&#xff0c;用于标识网络服务和应用程序。 但某些端口由于其开放性和易受攻击的…...

Redis集群模式之Redis Sentinel vs. Redis Cluster

在分布式系统环境中&#xff0c;Redis以其高性能、低延迟和丰富的数据结构而广受青睐。随着数据量的增长和访问需求的增加&#xff0c;单一Redis实例往往难以满足高可用性和扩展性的要求。为此&#xff0c;Redis提供了两种主要的集群模式&#xff1a;Redis Sentinel和Redis Clu…...

Leetcode 罗马数字转整数

代码的算法思想可以分为以下几步&#xff1a; 建立映射表&#xff1a; 首先&#xff0c;代码使用 HashMap 来存储罗马数字字符与其对应的整数值关系。例如&#xff0c;I 对应 1&#xff0c;V 对应 5&#xff0c;以此类推。这是为了方便后续快速查找每个罗马字符对应的整数值。 …...

东方通TongWeb替换Tomcat的踩坑记录

一、背景 由于信创需要&#xff0c;原来项目的用到的一些中间件、软件都要逐步替换为国产品牌&#xff0c;决定先从web容器入手&#xff0c;将Tomcat替换掉。在网上搜了一些资料&#xff0c;结合项目当前情况&#xff0c;考虑在金蝶AAS和东方通TongWeb里面选择&#xff0c;后又…...

ceph介绍和搭建

1 为什么要使用ceph存储 什么是对象存储&#xff1f; 对象存储并没有向文件系统那样划分为元数据区域和数据区域&#xff0c;而是按照不同的对象进行存储&#xff0c;而且每个对象内部维护着元数据和数据区域。因此每个对象都有自己独立的管理格式。 对象存储优点&#xff1a…...

树莓派安装FreeSWITCH

1、下载相关资源&#xff1a; # 假设所有资源都下载到/opt/目录下 cd /opt # 下载FreeSWITCH源码 git clone https://github.com/signalwire/freeswitch # 下载libks源码 git clone https://github.com/signalwire/libks # 下载sofia-sip源码 git clone https://github.com/fr…...

OpenSSL 生成根证书、中间证书和网站证书

OpenSSL 生成根证书、中间证书和网站证书 一、生成根证书&#xff08;ChinaRootCA&#xff09;二、生成中间 CA&#xff08;GuangDongCA&#xff09;三、生成网站证书&#xff08;gdzwfw&#xff09; 一、生成根证书&#xff08;ChinaRootCA&#xff09; 创建私钥&#xff1a; …...

MySQL核心业务大表归档过程

记录一下2年前的MySQL大表的归档&#xff0c;当时刚到公司&#xff0c;发现MySQL的业务核心库&#xff0c;超过亿条的有7张表&#xff0c;最大的表有9亿多条&#xff0c;有37张表超过5百万条&#xff0c;部分表行数如下&#xff1a; 在测试的MySQL环境 &#xff1a; pt-archiv…...

dapp获取钱包地址,及签名

npm install ethersimport {ethers} from ethers const accounts await ethereum.request({method: eth_requestAccounts}); // 获取钱包地址 this.form.address accounts[0] console.log("accounts:" this.address)const provider new ethers.BrowserProvider(…...

探索Dijkstra算法的普遍最优性:从经典算法到最新学术突破

引言 在计算机科学中&#xff0c;Dijkstra算法是解决单源最短路径问题的经典算法&#xff0c;尤其在地图导航、网络通信和机器人路径规划等领域有着广泛应用。近期&#xff0c;学术界在此算法上取得了重大突破&#xff1a;研究人员证明了Dijkstra算法的“普遍最优性”&#xff…...

‍️代码的华尔兹:在 Makefile 的指尖上舞动自动化的诗篇

文章目录 &#x1f636;‍&#x1f32b;️&#x1f636;‍&#x1f32b;️&#x1f636;‍&#x1f32b;️背景——一个优秀工程师必备技能&#x1f636;‍&#x1f32b;️&#x1f636;‍&#x1f32b;️&#x1f636;‍&#x1f32b;️一、&#x1f929;&#x1f929;快速了解…...

函数式编程Stream流(通俗易懂!!!)

目录 1.Lambda表达式 1.1 基本用法 1.2 省略规则 2.Stream流 2.1 常规操作 2.1.1 创建流 2.1.2 中间操作 filter map distinct sorted limit ​编辑skip flatMap 2.1.3 终结操作 foreach count max&min collect anyMatch allMatch noneMatch …...

数据分析:转录组差异fgsea富集分析

文章目录 介绍加载R包数据链接导入数据数据预处理DE testing: 2BP vs no-BP比较limma-voomLoad steroid dataIn No-BP patientsIn 2BP patientsCompare gene expression vs bacterial mass其他系统信息介绍 转录组差异fgsea富集分析是一种基于基因集的富集分析方法,它关注的是…...

在Django中安装、配置、使用CKEditor5,并将CKEditor5录入的文章展现出来,实现一个简单博客网站的功能

在Django中可以使用CKEditor4和CKEditor5两个版本&#xff0c;分别对应软件包django-ckeditor和django-ckeditor-5。原来使用的是CKEditor4&#xff0c;python manager.py makemigrations时总是提示CKEditor4有安全风险&#xff0c;建议升级到CKEditor5。故卸载了CKEditor4&…...

AI笔筒操作说明及应用场景

AI笔筒由来&#xff1a; 在快节奏的现代办公环境中&#xff0c;我们一直在寻找既能提升效率、增添便利&#xff0c;又能融入企业文化、展现个人品味的桌面伙伴。为此&#xff0c;我们特推出专为追求卓越、注重细节的您设计的AI笔筒礼品版&#xff0c;它集高科技与实用性于一身…...

Android自启动管控

1. 自启动管控需求来源 自启动、关联启动、交叉启动、推送启动等现象的泛滥除了对个人信息保护带来隐患外&#xff0c;还会导致占用过多的系统CPU和内存资源&#xff0c;造成系统卡顿、发热、电池消耗过快&#xff1b;还可能引入一些包含“恶意代码”的进程在后台隐蔽启动&…...

把握鸿蒙生态崛起的机遇:开发者视角的探讨

​ 大家好&#xff0c;我是程序员小羊&#xff01; 前言&#xff1a; 近年来&#xff0c;鸿蒙系统&#xff08;HarmonyOS&#xff09;的发展备受瞩目。随着其在智能手机、智能穿戴、车载系统和智能家居等领域的广泛应用&#xff0c;鸿蒙系统正逐渐形成与安卓、iOS并列的三足鼎立…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...