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

力扣每日一题: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 &#xff0c;找出其中 最长递增路径 的长度。 对于每个单元格&#xff0c;你可以往上&#xff0c;下&#xff0c;左&#xff0c;右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外&#xff08;即不允许环绕&#xff09;。 示例…...

树莓派部署yolov5实现目标检测(ubuntu22.04.3)

最近两天搞了一下树莓派部署yolov5&#xff0c;有点难搞&#xff08;这个东西有点老&#xff0c;版本冲突有些包废弃了等等&#xff09; 最后换到ubuntu系统弄了&#xff0c;下面是我的整体步骤&#xff08;建议先使能一下ssh&#xff08;最下面有&#xff09;&#xff0c;结合…...

2024 年最新使用 Wechaty 开源框架搭建部署微信机器人(微信群智能客服案例)

读取联系人信息 获取当前机器人账号全部联系人信息 bot.on(ready, async () > {console.log("机器人准备完毕&#xff01;&#xff01;&#xff01;")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.…...

什么是多路复用器滤波器

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

Severt和tomcat的使用(补充)

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

JavaEE初阶——多线程(一)

T04BF &#x1f44b;专栏: 算法|JAVA|MySQL|C语言 &#x1faf5; 小比特 大梦想 此篇文章与大家分享多线程的第一部分:引入线程以及创建多线程的几种方式 此文章是建立在前一篇文章进程的基础上的 如果有不足的或者错误的请您指出! 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.直接上代码&#xff0c;做好了注释&#xff08;初始化…...

2024-04-07(复盘前端)

---HTML 1.HTMl骨架 html&#xff1a;整个网页 head&#xff1a;网页头部&#xff0c;用来存放给浏览器看的信息&#xff0c;如css body&#xff1a;网页主体&#xff0c;用来存放给用户看的信息&#xff0c;例如图片和文字 2.标题标签中h1标签只能使用一次&#xff0c;其…...

SpringCloud学习(10)-SpringCloudAlibaba-Nacos服务注册、配置中心

Spring Cloud Alibaba 参考文档 Spring Cloud Alibaba 参考文档 nacos下载Nacos 快速开始 直接进入bin包 运行cmd命令&#xff1a;startup.cmd -m standalone 运行成功后通过http://localhost:8848/nacos进入nacos可视化页面&#xff0c;账号密码默认都是nacos Nacos服务注…...

OKCC外呼中心配置的电话系统规则

OKCC外呼中心配置电话系统规则可能涉及多个方面&#xff0c;包括呼叫路由、自动化流程、电话接听策略等。以下是一般步骤及注意事项&#xff1a; 呼叫路由配置&#xff1a; 确定呼叫中心的呼叫路由策略&#xff0c;包括如何分配呼叫给不同的坐席或部门。设置呼叫路由规则&#…...

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 提供的非常流行的、简单的性能测试工具&#xff0c;用于对 HTTP 服务器进行压力测试。下面是 ab 工具的一些基本使用方法。 安装 在大多数 Unix 系统中&#xff0c;ab 通常作为 Apache HTTP 服务器的一部分预装在系统中。你可以通过在终端…...

智能网联汽车自动驾驶数据记录系统DSSAD数据元素

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

Ubuntu 20.04.06 PCL C++学习记录(十八)

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

细雨踏春日,新会公安护平安

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

3d怎么在一块模型上开个孔---模大狮模型网

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

Python景区票务人脸识别系统(V2.0),附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

全球化业务的网络安全挑战

随着企业业务的全球化&#xff0c;跨国数据传输和用户跨地域访问成为常态。这不仅带来了巨大的商业机会&#xff0c;也带来了以下网络安全挑战&#xff1a; 数据泄露风险&#xff1a;跨国数据传输增加了数据被截获和泄露的风险。访问限制&#xff1a;某些地区可能对互联网内容…...

SQL简单优化思路

在编写SQL查询时&#xff0c;优化查询性能是一个重要的考虑因素&#xff0c;特别是在处理多表连接&#xff08;JOIN&#xff09;和子查询时。以下是一些具体的技巧和最佳实践&#xff0c;可以帮助你在保持相同返回值的前提下&#xff0c;降低SQL执行速度&#xff1a; 明确连接顺…...

外包干了25天,技术倒退明显

先说情况&#xff0c;大专毕业&#xff0c;18年通过校招进入湖南某软件公司&#xff0c;干了接近6年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落&#xff01; 而我已经在一个企业干了四年的功能…...

webpack环境配置分类结合vue使用

文件目录结构 按照目录结构创建好文件 控制台执行: npm install /config/webpack.common.jsconst path require(path) const {merge} require(webpack-merge) const {CleanWebpackPlugin} require(clean-webpack-plugin) const { VueLoaderPlugin } require(vue-loader); c…...

【蓝桥杯嵌入式】第十三届省赛(第二场)

目录 0 前言 1 展示 1.1 源码 1.2 演示视频 1.3 题目展示 2 CubeMX配置(第十三届省赛第二场真题) 2.1 设置下载线 2.2 HSE时钟设置 2.3 时钟树配置 2.4 生成代码设置 2.5 USART1 2.5.1 基本配置 2.5.2 NVIC 2.5.3 DMA 2.6 TIM 2.6.1 TIM2 2.6.2 TIM4 2.6.3 …...

maya节点绕轴旋转

目录 旋转后并尝试冻结变换 绕x轴旋转90度 使用Python脚本 使用图形界面 使用MEL脚本 绕y轴旋转90度 使用Python脚本 ok 旋转后并尝试冻结变换 import maya.cmds as cmdsdef adjust_root_rotation_for_export(joint_name):# 选择根节点cmds.select(joint_name)# 应用旋…...

如何水出第一篇SCI:SCI发刊历程,从0到1全过程经验分享!!!

如何水出第一篇SCI&#xff1a;SCI发刊历程&#xff0c;从0到1全路程经验分享&#xff01;&#xff01;&#xff01; 详细的改进教程以及源码&#xff0c;戳这&#xff01;戳这&#xff01;&#xff01;戳这&#xff01;&#xff01;&#xff01;B站&#xff1a;Ai学术叫叫兽e…...

SpringBoot表单防止重复提交

哪些因素会引起重复提交&#xff1f; 开发的项目中可能会出现下面这些情况&#xff1a; 前端下单按钮重复点击导致订单创建多次 网速等原因造成页面卡顿&#xff0c;用户重复刷新提交请求 黑客或恶意用户使用postman等http工具重复恶意提交表单 重复提交会带来哪些问题&…...

java面向对象.day17(什么是面向对象)

先认识&#xff1a;面向过程思想&#xff0c;面向对象思想 面向过程思想&#xff08;具体&#xff09; 步骤清晰简单&#xff0c;第一步做什么&#xff0c;第二步做什么.... 面对过程适合处理一些较为简单的问题 面向对象思想&#xff08;抽象&#xff09; 物以类聚&#x…...

mysql处理并发简单示例

处理并发的基本思路是使用锁来控制对共享资源的访问。在MySQL中&#xff0c;可以使用事务和行级锁来处理并发。 具体处理方式如下&#xff1a; 创建一个用于存储并发任务的MySQL表&#xff0c;该表包含一个自增的ID字段和任务名称字段。设置一个最大并发数量&#xff0c;用来…...

顺序表——功能实现

✨✨欢迎&#x1f44d;&#x1f44d;点赞☕️☕️收藏✍✍评论 个人主页&#xff1a;秋邱博客 所属栏目&#xff1a;C语言 &#xff08;感谢您的光临&#xff0c;您的光临蓬荜生辉&#xff09; 目录 1.0 前言 2.0 线性表 2.1 顺序表 2.2 顺序表的分类 2.3 顺序表功能的实现…...

广州网站建设公司/平台推广公司

linux对用户是透明的,这是用linux最大的感受. 做win开发的很多人其实都是linux/unix高手,这正说明的技术的相通性,思想是相同的,只是实现的工具,方式有些差异罢了.利用更加透明的linux进行学习,可以接触更多的开源项目,开拓思路,达到触类旁通的效果.从国内的开发环境而言&#…...

晋江网站建设报价/怎么在百度上推广产品

今日&#xff0c;星域CDN发布了直播新品“星域CDN•直播旗舰版”和“星域CDN•直播极速版”。网心科技CEO、迅雷联席CEO陈磊表示&#xff0c;星域CDN直播新品将以创新技术、腰斩价格、一站式百分百服务为视频直播行业带来更高品质、更低成本的解决方案。 网心科技CEO、迅雷联席…...

网站建设的优缺点/网络营销推广工具有哪些?

一、背景与架构(摘自官网) 随着互联网的发展&#xff0c;网站应用的规模不断扩大&#xff0c;常规的垂直应用架构已无法应对&#xff0c;分布式服务架构以及流动计算架构势在必行&#xff0c;亟需一个治理系统确保架构有条不紊的演进。 可以看出Dubbo的架构很像生产者-消费者…...

wordpress 展开收缩/百度首页纯净版

预处理指令 1.C语言在对源程序进行编译之前&#xff0c;会先对一些特殊的预处理指令作解释(比如之前使用的#include文件包含指令)&#xff0c; 产生一个新的源程序(这个过程称为编译预处理),之后再进行通常的编译 2.为了区分预处理指令和一般的C语句&#xff0c;所有预处理指令…...

网站上papi酱做的音频/搜索引擎网址有哪些

&#xff08;-1&#xff09;写在前面 这个图片是我从网上下载的&#xff0c;向这位前辈致敬。图片资源在我的百度云盘里。http://pan.baidu.com/s/1nvfJHdZ 我用的是chrome49&#xff0c;JQuery3.0&#xff0c;案例并没有考虑浏览器兼容问题&#xff0c;如果你看不到动画效果…...

隐藏wordpress目录/5188关键词挖掘工具

学习 Bootstrap 5 之 表格表格 (Tables)1. 创建表格(1). 使用原生的表格标签(2). 使用Bootstrap 5 的提供的表格标签类(3). 原生与Bootstrap创建出来的表格的对比2. 表格颜色样式(1). 表格颜色样式的效果(2). 表格颜色样式的使用1). 用于 <table> 标签2). 用于 <thead…...