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

C++算法:矩阵中的最长递增路径

涉及知识点

拓扑排序

题目

给定一个 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

2023年一月版

class Solution {
public:
int longestIncreasingPath(vector<vector>& matrix) {
m_r = matrix.size();
m_c = matrix[0].size();
m_dp.assign(m_r, vector(m_c, -1));
std::map<int,vector<pair<int,int>>> mVRC;
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
mVRC[matrix[r][c]].emplace_back(r, c);
}
}
for (auto& it : mVRC)
{
for (auto& rc : it.second)
{
m_dp[rc.first][rc.second] = Test(matrix, rc.first, rc.second);
}
}
int iMax = 0;
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
iMax = max(iMax, m_dp[r][c]);
}
}
return iMax;
}
int Test(const vector<vector>& matrix,int r, int c)
{
int iMax = 0;
if ((r > 0) && (matrix[r][c] > matrix[r - 1][c]))
{
iMax = max(iMax,m_dp[r-1][c] );
}
if ((r +1 < m_r ) && (matrix[r][c] > matrix[r + 1][c]))
{
iMax = max(iMax, m_dp[r + 1][c]);
}
if ((c > 0) && (matrix[r][c] > matrix[r][c-1]))
{
iMax = max(iMax, m_dp[r][c-1]);
}
if ((c + 1 < m_c) && (matrix[r][c] > matrix[r][c + 1]))
{
iMax = max(iMax, m_dp[r][c + 1]);
}
return iMax + 1;
}
int m_r;
int m_c;
vector<vector> m_dp;
};

2023年8月版

class Solution {
public:
int longestIncreasingPath(vector<vector>& matrix) {
m_r = matrix.size();
m_c = matrix.front().size();
m_iMaskNum = m_r * m_c;
//生成邻接表
vector<vector> vNeiBo(m_iMaskNum);
vector vInDeg(m_iMaskNum);
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
auto Add = [this,&matrix, &vNeiBo,&vInDeg](int curMask, int curValue, int r, int c)
{
if ((r < 0) || (r >= m_r))
{
return;
}
if ((c < 0) || (c >= m_c))
{
return;
}
if (curValue > matrix[r][c])
{
vNeiBo[r * m_c + c].emplace_back(curMask);
vInDeg[curMask]++;
}
};
Add(r * m_c + c, matrix[r][c], r + 1, c);
Add(r * m_c + c, matrix[r][c], r - 1, c);
Add(r * m_c + c, matrix[r][c], r, c + 1);
Add(r * m_c + c, matrix[r][c], r, c - 1);
}
}
//top排序
queue que;
vector vLen(m_iMaskNum, 0);
for (int i = 0; i < m_iMaskNum; i++)
{
if (0 == vInDeg[i])
{
que.emplace(i);
vLen[i] = 1;
}
}
while (que.size())
{
const int cur = que.front();
que.pop();
for (const auto& next : vNeiBo[cur])
{
if (–vInDeg[next] == 0)
{
vLen[next] = vLen[cur] + 1;
que.emplace(next);
}
}
}
return *std::max_element(vLen.begin(), vLen.end());
}
int m_r;
int m_c;
int m_iMaskNum;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

| 洒家想对大家说的话
|
|-|
|闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。|
| 墨家名称的来源:有所得以墨记之。 |
|如果程序是一条龙,那算法就是他的是睛|

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境:

VS2022 C++17

相关文章:

C++算法:矩阵中的最长递增路径

涉及知识点 拓扑排序 题目 给定一个 m x n 整数矩阵 matrix &#xff0c;找出其中 最长递增路径 的长度。 对于每个单元格&#xff0c;你可以往上&#xff0c;下&#xff0c;左&#xff0c;右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外&#xff08;即不允…...

OpenWRT配置SFTP远程文件传输,让数据分享更安全

文章目录 前言 1. openssh-sftp-server 安装2. 安装cpolar工具3.配置SFTP远程访问4.固定远程连接地址 前言 本次教程我们将在OpenWRT上安装SFTP服务&#xff0c;并结合cpolar内网穿透&#xff0c;创建安全隧道映射22端口&#xff0c;实现在公网环境下远程OpenWRT SFTP&#xf…...

已解决:rm: 无法删除“/opt/module/zookeeper-3.4.10/zkData/zookeeper_server.pid“: 权限不够

解决&#xff1a; ZooKeeper JMX enabled by default Using config: /opt/module/zookeeper-3.4.10/bin/../conf/zoo.cfg Stopping zookeeper ... /opt/module/zookeeper-3.4.10/bin/zkServer.sh: 第 182 行:kill: (4149) - 不允许的操作 rm: 无法删除"/opt/module/zooke…...

Flink(四)【DataStream API - Source算子】

前言 今天开始学习 DataStream 的 API &#xff0c;这一块是 Flink 的核心部分&#xff0c;我们不去学习 DataSet 的 API 了&#xff0c;因为从 Flink 12 开始已经实现了流批一体&#xff0c; DataSet 已然是被抛弃了。忘记提了&#xff0c;从这里开始&#xff0c;我开始换用 F…...

GIS入门,xyz地图瓦片是什么,xyz数据格式详解,如何发布离线XYZ瓦片到nginx或者tomcat中

XYZ介绍 XYZ瓦片是一种在线地图数据格式,由goole公司开发。 与其他瓦片地图类似,XYZ瓦片将地图数据分解为一系列小的图像块,以提高地图显示效率和性能。 XYZ瓦片提供了一种开放的地图平台,使开发者可以轻松地将地图集成到自己的应用程序中。同时,它还提供了高分辨率图像和…...

[工业自动化-14]:西门子S7-15xxx编程 - 软件编程 - STEP7 TIA博途是全集成自动化软件TIA portal快速入门

目录 一、TIA博途是全集成自动化软件TIA portal快速入门 1.1 简介 1.2 软件常用界面 1.3 软件安装的电脑硬件要求 1.4 入口 1.5 主界面 二、PLC软件编程包含哪些内容 2.1 概述 2.2 电机运动控制 一、TIA博途是全集成自动化软件TIA portal快速入门 1.1 简介 Siemens …...

【教3妹学编程-算法题】Range 模块

3妹&#xff1a;哈哈哈哈哈哈哈哈 2哥 : 3妹看什么呢&#xff0c;笑的这么开森 3妹&#xff1a;2哥你快来看啊&#xff0c;成都欢乐谷的NPC模仿“唐僧”&#xff0c; 太搞笑了。 2哥 : 哦这个我也看到了&#xff0c;真的是唯妙唯肖&#xff0c;不能说像&#xff0c;只能说一模一…...

SpringBoot+MybatisPlus Restful示例

增删改查,分页 CREATE TABLE tbl_book ( id int NOT NULL AUTO_INCREMENT, type varchar(20) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL, name varchar(50) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL, desc_ription varchar(255) CHAR…...

【数据结构】树与二叉树(十一):二叉树的层次遍历(算法LevelOrder)

文章目录 5.2.1 二叉树二叉树性质引理5.1&#xff1a;二叉树中层数为i的结点至多有 2 i 2^i 2i个&#xff0c;其中 i ≥ 0 i \geq 0 i≥0。引理5.2&#xff1a;高度为k的二叉树中至多有 2 k 1 − 1 2^{k1}-1 2k1−1个结点&#xff0c;其中 k ≥ 0 k \geq 0 k≥0。引理5.3&…...

【PyQt】(自制类)处理鼠标点击逻辑

写了个自认为还算不错的类&#xff0c;用于简化mousePressEvent、mouseMoveEvent和mouseReleaseEvent中的鼠标信息。 功能有以下几点&#xff1a; 鼠标当前状态&#xff0c;包括鼠标左/中/右键和单击/双击/抬起鼠标防抖(仅超出一定程度时才判断鼠标发生了移动)&#xff0c;灵…...

JAVA IDEA 下载

超简单步骤一&#xff1a; IntelliJ IDEA 官方下载链接 点击以上链接进入下图&#xff0c;点击下载 继续点下载&#xff0c;然后等待下载完后打开安装包即可 步骤二&#xff1a; 打开下好的安装包&#xff0c;点击Browse...我们把它下载到自己喜欢的地方&#xff08;主要是别占…...

DevOps简介

DevOps简介 1、DevOps的起源2、什么是DevOps3、DevOps的发展现状4、DevOps与虚拟化、容器 1、DevOps的起源 上个世纪40年代&#xff0c;世界上第一台计算机诞生。计算机离不开程序&#xff08;Program&#xff09;驱动&#xff0c;而负责编写程序的人&#xff0c;被称为程序员&…...

体验前所未有的显示器管理体验:BetterDisplay Pro Mac

在现代的数字化时代&#xff0c;显示器是我们日常生活和工作中不可或缺的一部分。从笔记本电脑到台式机&#xff0c;从平板电脑到手机&#xff0c;几乎所有的电子设备都配备了显示器。然而&#xff0c;对于专业人士和从事设计行业的人来说&#xff0c;仅仅依靠系统自带的显示器…...

python用pyinstaller打包exe,去掉黑窗口

使用Python编写程序将Python脚本打包成可执行文件&#xff08;EXE&#xff09;,但是会有一个命令框产生&#xff0c;很烦&#xff0c;所以&#xff0c;去掉这个框 1&#xff0c;安装pyinstaller pip install pyinstaller2&#xff0c;打包产生cmd命令框 pyinstaller --onefi…...

如何关闭Windows Defender(亲测可行!!非常简单)

一、背景 Windows Defender&#xff08;简称WD&#xff09;真的太讨厌了&#xff0c;经常给你报你下载的文件是病毒&#xff0c;且不说真的是不是病毒&#xff0c;它都不询问直接删。 另外聚资料显示WD还会不合时宜地执行扫描导致系统变慢&#xff08;不会在合适的、空闲的时…...

【objectarx.net】创建多重引线

创建多重引线...

【objectarx.net】创建组,列出所有组,查找实体所在的组

创建组,列出所有组...

Llama2通过llama.cpp模型量化 WindowsLinux本地部署

Llama2通过llama.cpp模型量化 Windows&Linux本地部署 什么是LLaMA 1 and 2 LLaMA&#xff0c;它是一组基础语言模型&#xff0c;参数范围从7B到65B。在数万亿的tokens上训练的模型&#xff0c;并表明可以专门使用公开可用的数据集来训练最先进的模型&#xff0c;而无需求…...

Coding面试题之手写线程池

原理图 JDK线程池原理 实现代码 1.线程类&#xff08;PoolThread&#xff09; 这个类用于执行任务队列中的任务。 public class PoolThread extends Thread {private final Queue<Runnable> taskQueue;private boolean isStopped false;private long lastTaskTime …...

【objectarx.net】删除零长度曲线和获取零长度曲线的数量

删除零长度曲线和获取零长度曲线的数量...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...