当前位置: 首页 > 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;某些地区可能对互联网内容…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...

React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构

React 实战项目&#xff1a;微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇&#xff01;在前 29 篇文章中&#xff0c;我们从 React 的基础概念逐步深入到高级技巧&#xff0c;涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...

数据分析六部曲?

引言 上一章我们说到了数据分析六部曲&#xff0c;何谓六部曲呢&#xff1f; 其实啊&#xff0c;数据分析没那么难&#xff0c;只要掌握了下面这六个步骤&#xff0c;也就是数据分析六部曲&#xff0c;就算你是个啥都不懂的小白&#xff0c;也能慢慢上手做数据分析啦。 第一…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架

文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理&#xff1a;检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目&#xff1a;RankRAG&#xff1a;Unifying Context Ranking…...