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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/189116.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

写一下关于部署项目到服务器的心得(以及遇到的难处)

首先要买个服务器(本人的是以下这个) 这里我买的是宝塔面板的,没有宝塔面板的也可以自行安装 点击登录会去到以下页面 在这个界面依次执行下面命令会看到账号和密码和宝塔面板内外网地址 sudo -s bt 14点击地址就可以跳转宝塔对应的内外网页面 然后使用上述命令提供的账号密…

C语言 预处理详解

目录 1.预定义符号 2.#define 2.1#define 定义标识符 2.2#define 定义宏 2.3#define 替换规则 2.4#和## 2.4.1# 的作用 2.4.2## 的作用 2.5 带有副作用的宏参数 2.6宏和函数的对比 对比 **2.7内联函数 2.8命名约定 3.#undef **4.命令行定义 5.条件编译 常…

ElasticSearch中常见的分词器介绍

文章目录 ElasticSearch中常见的分词器介绍前言分词器的作用如何指定分词器分词器的组成分词器的类型标准分词器空格分词器简单分词器关键词分词器停用词分词器IK分词器NGram分词器正则匹配分词器语言分词器自定义分词器 ElasticSearch中常见的分词器介绍 前言 ElasticSearch是…

【C++】stack,queue和deque

stack的介绍 stack是一种容器适配器&#xff0c;专门用在具有后进先出操作的上下文环境中&#xff0c;其删除只能从容器的一端进行元素的插入与提取操作。stack是作为容器适配器被实现的&#xff0c;容器适配器即是对特定类封装作为其底层的容器&#xff0c;并提供一组特定 的成…

jupyter notebook中markdown改变图像大小

文章目录 &#x1f56e;原始图像&#x1f56e;改变图像大小&#x1f56e;使图像靠左 在 jupyter notebook中&#xff0c;导入的图片过大&#xff0c;想要改变图像的大小 &#x1f56e;原始图像 &#x1f56e;改变图像大小 复制小括号里面的内容到src后面&#xff0c;满足<…

Django的ORM操作

文章目录 1.ORM操作1.1 表结构1.1.1 常见字段和参数1.1.2 表关系 2.ORM2.1 基本操作2.2 连接数据库2.3 基础增删改查2.3.1 增加2.3.2 查找2.3.4 删除2.3.4 修改 1.ORM操作 orm&#xff0c;关系对象映射&#xff0c;本质翻译的。 1.1 表结构 实现&#xff1a;创建表、修改表、…

【ElasticSearch】学习使用DSL和RestClient编写查询语句

文章目录 DSL和RestClient的学习前言1、DSL查询文档1.1 查询分类1.2 全文检索查询1.21 全文检索概述1.2.2 基本使用 1.3 精确查询1.3.1 term查询1.3.2 range查询 1.4 地理坐标查询1.4.1 geo_bounding_box查询1.4.2 geo_distance查询 1.5 复合查询1.5.1 常见相关性算法1.5.2 算分…

WebRTC简介及使用

文章目录 前言一、WebRTC 简介1、webrtc 是什么2、webrtc 可以做什么3、数据传输需要些什么4、SDP 协议5、STUN6、TURN7、ICE 二、WebRTC 整体框架三、WebRTC 功能模块1、视频相关①、视频采集---video_capture②、视频编解码---video_coding③、视频加密---video_engine_encry…

SpringBoot系列-2 自动装配

背景&#xff1a; Spring提供了IOC机制&#xff0c;基于此我们可以通过XML或者注解配置&#xff0c;将三方件注册到IOC中。问题是每个三方件都需要经过手动导入依赖、配置属性、注册IOC&#xff0c;比较繁琐。 基于"约定优于配置"原则的自动装配机制为该问题提供了一…

Unity中全局光照GI的总结

文章目录 前言一、在编写Shader时&#xff0c;有一些隐蔽的Bug不会直接报错&#xff0c;我们需要编译一下让它显示出来&#xff0c;方便修改我们选择我们的Shader&#xff0c;点击编译并且展示编译后的Shader后的内容&#xff0c;隐蔽的Bug就会暴露出来了。 二、我们大概回顾一…

Python 潮流周刊#26:requests3 的现状

△点击上方“Python猫”关注 &#xff0c;回复“1”领取电子书 你好&#xff0c;我是猫哥。这里每周分享优质的 Python、AI 及通用技术内容&#xff0c;大部分为英文。本周刊开源&#xff0c;欢迎投稿[1]。另有电报频道[2]作为副刊&#xff0c;补充发布更加丰富的资讯。 &#…

每天一点python——day66

#每天一点Python——66 #字符串的分隔 #如图&#xff1a; #方法①split()从左开始分隔&#xff0c;默认空格为分割字符&#xff0c;返回值是一个列表 shello world jisuanji#首先创建一个字符串 list1s.split() print(list1)#输出结果是&#xff1a;[hello, world, jisuanji]注…

No179.精选前端面试题,享受每天的挑战和学习

🤍 前端开发工程师(主业)、技术博主(副业)、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云课上架的前后端实战课程《Vue.js 和 Egg.js 开发企业级健康管理项目》、《带你从入…

python实现炒股自动化,个人账户无门槛量化交易的开始

本篇作为系列教程的引子&#xff0c;对股票量化程序化自动交易感兴趣的朋友可以关注我&#xff0c;现在只是个粗略计划&#xff0c;后续会根据需要重新调整&#xff0c;并陆续添加内容。 股票量化程序化自动交易接口 很多人在找股票个人账户实现程序化自动交易的接口&#xff0…

【笔记】结合P02项目——maven继承与聚合

maven的继承关系 P02项目大概是这个样子&#xff0c;下图展示的是其父工程 父工程配置了parent依赖springb-boot-starter-parent&#xff0c;子工程配置其parant为父工程 子工程引用common子工程 maven的版本锁定 管理子工程的版本号问题 父工程添加dependencyManageMent…

【Docker】Docker 网络

引言 Docker是一个开源的应用容器引擎&#xff0c;它允许开发者将应用及其依赖打包到一个可移植的容器中&#xff0c;然后发布到任何流行的Linux机器或Windows机器上&#xff0c;也可以实现虚拟化。Docker的主要优势之一是其网络功能&#xff0c;而网络功能的核心就是网络驱动…

剖析WPF模板机制的内部实现

剖析WPF模板机制的内部实现 众所周知&#xff0c;在WPF框架中&#xff0c;Visual类是可以提供渲染&#xff08;render&#xff09;支持的最顶层的类&#xff0c;所有可视化元素&#xff08;包括UIElement、FrameworkElment、Control等&#xff09;都直接或间接继承自Visual类。…

Maya 2024 for Mac(3D建模软件)

Maya 2024是一款三维计算机图形软件&#xff0c;具有强大的建模、动画、渲染、特效等功能&#xff0c;广泛应用于影视、游戏、广告等行业。以下是Maya 2024软件的主要功能介绍&#xff1a; 建模&#xff1a;Maya 2024具有强大的建模工具&#xff0c;包括多边形建模、曲面建模、…

Leetcode100120. 找出强数对的最大异或值 I

Every day a Leetcode 题目来源&#xff1a;100120. 找出强数对的最大异或值 I 解法1&#xff1a;模拟 枚举 2 遍数组 nums 的元素&#xff0c;更新最大异或值。 代码&#xff1a; /** lc appleetcode.cn id100120 langcpp** [100120] 找出强数对的最大异或值 I*/// lc c…

【大模型】大语言模型语料下载

文章目录 概述Hugging Faceobs操作git-lfs例子RedPajama-Data-1TSlimPajama-627B/git clone续传 数据格式参考资料 概述 大模型训练中语料是非常重要的&#xff0c;目前公网上有各种各样的语料可以供下载&#xff0c;但是不可能每个用户、每次训练任务都通过公网去拉取语料&am…