力扣每日一题:LCR112--矩阵中的最长递增路径
题目
给定一个 m x n
整数矩阵 matrix
,找出其中 最长递增路径 的长度。
对于每个单元格,你可以往上,下,左,右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。
示例 1:
输入:matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出:4
解释:最长递增路径为 [1, 2, 6, 9]
。
示例 2:
输入:matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出:4
解释:最长递增路径是 [3, 4, 5, 6]
。注意不允许在对角线方向上移动。
示例 3:
输入:matrix = [[1]] 输出:1
提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231 - 1
注意:本题与主站 329 题相同: . - 力扣(LeetCode)
请问您在哪类招聘中遇到此题?
1/5
社招
校招
实习
未遇到
通过次数
16.3K
提交次数
28.2K
通过率
57.6%
记忆化搜索
遍历所有的点[i][j],求出从[i][j]为起点时的递增路径长度,所有长度的最大值即为所求。正常搜索时会有很多重复操作,所以加上一个记忆化的数组f来记录从[i][j]出发的路径长度,初始化为0,在搜索[i][j]这个点时,如果f[i][j]非零,则直接返回f[i][j]的值。
class Solution {
public:int tx[4]={-1,1,0,0};int ty[4]={0,0,-1,1};int m;int n;int dfs(int x,int y,vector<vector<int>>& matrix,vector<vector<int>>& f){if(f[x][y]!=0){return f[x][y];}++f[x][y];for(int i=0;i<4;i++){int dx=x+tx[i];int dy=y+ty[i];if(dx>=0&&dx<m&&dy>=0&&dy<n&&matrix[dx][dy]>matrix[x][y]){f[x][y]=max(f[x][y],dfs(dx,dy,matrix,f)+1);}}return f[x][y];}int longestIncreasingPath(vector<vector<int>>& matrix) {m=matrix.size();n=matrix[0].size();int maxLen=0;vector<vector<int>> f(m,vector<int>(n,0));for(int i=0;i<m;i++){for(int j=0;j<n;j++){maxLen=max(maxLen,dfs(i,j,matrix,f));}}return maxLen;}
};
拓补排序
在一条上升路径中,必须先经过值小的点,才能再经过值大的点。也就是说在这个图中,值更小是值更大的先决条件,并且这个图中所有的路径是不可能构成环的。对于这种存在先决条件的无环有向图,可以用拓补排序来解决。
核心代码模式(官解)
class Solution {
public:static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int rows, columns;int longestIncreasingPath(vector< vector<int> > &matrix) {if (matrix.size() == 0 || matrix[0].size() == 0) {return 0;}rows = matrix.size();columns = matrix[0].size();auto outdegrees = vector< vector<int> > (rows, vector <int> (columns));for (int i = 0; i < rows; ++i) {for (int j = 0; j < columns; ++j) {for (int k = 0; k < 4; ++k) {int newRow = i + dirs[k][0], newColumn = j + dirs[k][1];if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] > matrix[i][j]) {++outdegrees[i][j];}}}}queue < pair<int, int> > q;for (int i = 0; i < rows; ++i) {for (int j = 0; j < columns; ++j) {if (outdegrees[i][j] == 0) {q.push({i, j});}}}int ans = 0;while (!q.empty()) {++ans;int size = q.size();for (int i = 0; i < size; ++i) {auto cell = q.front(); q.pop();int row = cell.first, column = cell.second;for (int k = 0; k < 4; ++k) {int newRow = row + dirs[k][0], newColumn = column + dirs[k][1];if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] < matrix[row][column]) {--outdegrees[newRow][newColumn];if (outdegrees[newRow][newColumn] == 0) {q.push({newRow, newColumn});}}}}}return ans;}
};
自己输入数据的模式
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
int n,m;
int height[105][105];
int outdegrees[105][105];
int tx[]={-1,1,0,0};
int ty[]={0,0,-1,1};
int main()
{cin>>n>>m;queue<pair<int,int>> p;int maxLen=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>height[i][j];outdegrees[i][j]=0;}}//初始化出度,出度为0的入队for(int i=0;i<n;i++){for(int j=0;j<m;j++){for(int k=0;k<4;k++){int dx=i+tx[k];int dy=j+ty[k];if(dx>=0&&dx<n&&dy>=0&&dy<m&&height[dx][dy]>height[i][j])++outdegrees[i][j];}if(outdegrees[i][j]==0)p.push({i,j});}}//开始拓补排序,类似于广度优先while(!p.empty()){++maxLen;int size=p.size();for(int i=0;i<size;i++){pair<int,int> cur=p.front();p.pop();int x=cur.first,y=cur.second;//更新相邻节点的出度为0的出度for(int k=0;k<4;k++){int dx=x+tx[k];int dy=y+ty[k];if(dx>=0&&dx<n&&dy>=0&&dy<n&&height[dx][dy]<height[x][y]){--outdegrees[dx][dy];if(outdegrees[dx][dy]==0){p.push({dx,dy});}}}}}cout<<maxLen;
}
相关文章:

力扣每日一题:LCR112--矩阵中的最长递增路径
题目 给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。 对于每个单元格,你可以往上,下,左,右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。 示例…...

树莓派部署yolov5实现目标检测(ubuntu22.04.3)
最近两天搞了一下树莓派部署yolov5,有点难搞(这个东西有点老,版本冲突有些包废弃了等等) 最后换到ubuntu系统弄了,下面是我的整体步骤(建议先使能一下ssh(最下面有),结合…...

2024 年最新使用 Wechaty 开源框架搭建部署微信机器人(微信群智能客服案例)
读取联系人信息 获取当前机器人账号全部联系人信息 bot.on(ready, async () > {console.log("机器人准备完毕!!!")let contactList await bot.Contact.findAll()for (let index 0; index < contactList.length; index) {…...

Redis从入门到精通(九)Redis实战(六)基于Redis队列实现异步秒杀下单
↑↑↑请在文章开头处下载测试项目源代码↑↑↑ 文章目录 前言4.5 分布式锁-Redisson4.5.4 Redission锁重试4.5.5 WatchDog机制4.5.5 MutiLock原理 4.6 秒杀优化4.6.1 优化方案4.6.2 完成秒杀优化 4.7 Redis消息队列4.7.1 基于List实现消息队列4.7.2 基于PubSub的消息队列4.7.…...

什么是多路复用器滤波器
本章将更深入地介绍多路复用器滤波器,以及它们如何用于各种应用中。您将了解到多路复用器如何帮助设计人员创造出更复杂的无线产品。 了解多路复用器 多路复用器是一组射频(RF)滤波器,它们组合在一起,但不会彼此加载,可以在输出之…...

Severt和tomcat的使用(补充)
打包程序 在pom.xml中添加上述代码之后打包时会生成war包并且包的名称是test 默认情况打的是jar包.jar里量但是tomcat要求的是war包. war包Tomcat专属的压缩包. war里面不光有.class还有一些tomcat要求的配置文件(web.xml等)还有前端的一些代码(html, css, js) 点击其右边的m…...

JavaEE初阶——多线程(一)
T04BF 👋专栏: 算法|JAVA|MySQL|C语言 🫵 小比特 大梦想 此篇文章与大家分享多线程的第一部分:引入线程以及创建多线程的几种方式 此文章是建立在前一篇文章进程的基础上的 如果有不足的或者错误的请您指出! 1.认识线程 我们知道现代的cpu大多都是多核心…...
MongoDB主从复制模式基于银河麒麟V10系统
MongoDB主从复制模式基于银河麒麟V10系统 背景介绍 MongoDB自4.0版本开始已经不再建议使用传统的master/slave复制架构,而是全面采用了复制集(Replica Sets)作为标准的复制和高可用性解决方案。 复制集是MongoDB的一种数据复制和高可用性机制,通过异步同步数据至多个服务…...

Vue使用高德地图
1.在高德平台注册账号 2.我的 > 管理管理中添加Key 3.安装依赖 npm i amap/amap-jsapi-loader --save 或 yarn add amap/amap-jsapi-loader --save 4.导入 AMapLoade import AMapLoader from amap/amap-jsapi-loader; 5.直接上代码,做好了注释(初始化…...
2024-04-07(复盘前端)
---HTML 1.HTMl骨架 html:整个网页 head:网页头部,用来存放给浏览器看的信息,如css body:网页主体,用来存放给用户看的信息,例如图片和文字 2.标题标签中h1标签只能使用一次,其…...

SpringCloud学习(10)-SpringCloudAlibaba-Nacos服务注册、配置中心
Spring Cloud Alibaba 参考文档 Spring Cloud Alibaba 参考文档 nacos下载Nacos 快速开始 直接进入bin包 运行cmd命令:startup.cmd -m standalone 运行成功后通过http://localhost:8848/nacos进入nacos可视化页面,账号密码默认都是nacos Nacos服务注…...
OKCC外呼中心配置的电话系统规则
OKCC外呼中心配置电话系统规则可能涉及多个方面,包括呼叫路由、自动化流程、电话接听策略等。以下是一般步骤及注意事项: 呼叫路由配置: 确定呼叫中心的呼叫路由策略,包括如何分配呼叫给不同的坐席或部门。设置呼叫路由规则&#…...
AI推介-大语言模型LLMs论文速览(arXiv方向):2024.03.31-2024.04.05
文章目录~ 1.AutoWebGLM: Bootstrap And Reinforce A Large Language Model-based Web Navigating Agent2.Training LLMs over Neurally Compressed Text3.Unveiling LLMs: The Evolution of Latent Representations in a Temporal Knowledge Graph4.Visualization-of-Thought …...
性能测试工具 ab(Apache Bench)使用详解
Apache Bench (ab) 是一个由 Apache 提供的非常流行的、简单的性能测试工具,用于对 HTTP 服务器进行压力测试。下面是 ab 工具的一些基本使用方法。 安装 在大多数 Unix 系统中,ab 通常作为 Apache HTTP 服务器的一部分预装在系统中。你可以通过在终端…...

智能网联汽车自动驾驶数据记录系统DSSAD数据元素
目录 第一章 数据元素分级 第二章 数据元素分类 第三章 数据元素基本信息表 表1 车辆及自动驾驶数据记录系统基本信息 表2 车辆状态及动态信息 表3 自动驾驶系统运行信息 表4 行车环境信息 表5 驾驶员操作及状态信息 第一章 数据元素分级 自动驾驶数据记录系统记录的数…...

Ubuntu 20.04.06 PCL C++学习记录(十八)
[TOC]PCL中点云分割模块的学习 学习背景 参考书籍:《点云库PCL从入门到精通》以及官方代码PCL官方代码链接,,PCL版本为1.10.0,CMake版本为3.16 学习内容 PCL中实现欧式聚类提取。在点云处理中,聚类是一种常见的任务,它将点云数据划分为多…...

细雨踏春日,新会公安护平安
春雨起,清明至。又是一年春草绿,又是一年清明时。细雨踏春日,思怀故人时,是哀思,亦是相聚。新会公安一抹抹葵乡春日“警”色坚守岗位,确保清明祭扫平稳有序,为人民群众的平安保驾护航。 为确保2…...

3d怎么在一块模型上开个孔---模大狮模型网
在进行3D建模时,有时候需要在模型上创建孔,以实现特定的设计需求或功能。无论是为了添加细节,还是为了实现功能性的要求,创建孔都是常见的操作之一。本文将介绍在3D模型上创建孔的几种常用方法,帮助您轻松实现这一目标…...

Python景区票务人脸识别系统(V2.0),附源码
博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专栏推荐订阅👇…...
全球化业务的网络安全挑战
随着企业业务的全球化,跨国数据传输和用户跨地域访问成为常态。这不仅带来了巨大的商业机会,也带来了以下网络安全挑战: 数据泄露风险:跨国数据传输增加了数据被截获和泄露的风险。访问限制:某些地区可能对互联网内容…...

19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...