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

矩阵中的最长递增路径

题目链接

矩阵中的最长递增路径

题目描述


注意点

  • 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)

解答思路

  • 因为最长递增路径一定是连续的,所以想到使用深度优先遍历来做。如果只使用深度优先遍历会导致超时(同一个节点的最长递增路径可能会计算多次),所以考虑引入动态规划存储每个节点的最长递增路径。除此之外,还要进行剪枝,主要是解决边界问题和移动后的值小于当前值的情况

代码

class Solution {int row;int col;int[][] directions;public int longestIncreasingPath(int[][] matrix) {int res = 0;row = matrix.length;col = matrix[0].length;directions = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int[][] dp = new int[row][col];for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {res = Math.max(res, findMaxPath(matrix, dp, i, j));}}return res;}public int findMaxPath(int[][] matrix, int[][] dp, int i, int j) {if (dp[i][j] != 0) {return dp[i][j];}int maxPath = 0;for (int[] direction : directions) {int x = i + direction[0];int y = j + direction[1];if (x < 0 || x >= row || y < 0 || y >= col) {continue;}if (matrix[x][y] <= matrix[i][j]) {continue;}maxPath = Math.max(maxPath, findMaxPath(matrix, dp, x, y));}dp[i][j] = maxPath + 1;return dp[i][j];}
}

关键点

  • 深度优先遍历的思想
  • 动态规划的思想
  • 注意边界问题

相关文章:

矩阵中的最长递增路径

题目链接 矩阵中的最长递增路径 题目描述 注意点 不能 在 对角线 方向上移动或移动到 边界外&#xff08;即不允许环绕&#xff09; 解答思路 因为最长递增路径一定是连续的&#xff0c;所以想到使用深度优先遍历来做。如果只使用深度优先遍历会导致超时&#xff08;同一个…...

vue2 element 弹出框拖拽会出现一层阴影问题

问题如图所示&#xff1a; 因增加 draggable 属性导致我弹窗表单清空文本框时&#xff0c;从右向左选中字体会出现拖拽阴影效果 去掉 draggable 即可 <template><div class"sys-jobTrigger-container"><el-dialog:visible.sync"state.isShowD…...

idea git回滚之前提交记录

提交代码时&#xff0c;如果不小心提交了不需要提交的内容&#xff0c;在本地仓库中&#xff0c;此时需要回滚版本&#xff0c;如何回滚 1.打开git控制台&#xff0c;左下角git,选择要处理的分支&#xff0c;选择刷新获取最新git提交记录 2&#xff09;选中自己commit需要回滚…...

什么是Modbus协议?

Modbus协议是一种在工业自动化领域广泛应用的通信协议&#xff0c;它允许不同设备之间进行可靠的数据交换和控制。该协议最初由Modicon公司于1979年创建&#xff0c;旨在提供一种简单而有效的方法&#xff0c;使PLC&#xff08;可编程逻辑控制器&#xff09;和其他自动化设备能…...

222.【2023年华为OD机试真题(C卷)】分配土地(扫描线算法-JavaPythonC++JS实现)

🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(Java&Python&C++&JS分别实现),详细代码讲解,助你深入学习,深度掌握! 文章目录 一. 题目-分配土地二.解题思路三.题解代码Python题解代码…...

Linux网络编程(一-网络相关知识点)

目录 一、网络相关知识简介 二、网络协议的分层模型 2.1 OSI七层模型 2.2 TCP/IP五层模型 2.3 协议层报文间的封装与拆封 三、IP协议 3.1 MAC地址 3.2 IP地址 3.3 MAC地址与IP地址区别 一、网络相关知识简介 互联网通信的本质是数字通信&#xff0c;任何数字通信都离…...

IO进程线程day5

1.实现互斥机制 #include <head.h>char buf[128]; //全局数组&#xff0c;临界资源//1、创建一个互斥锁 pthread_mutex_t mutex;//定义分支线程 void *task(void *arg) {while(1){//3、获取锁资源pthread_mutex_lock(&mutex);printf("分支线程中&…...

读元宇宙改变一切笔记04_网络化

1. 思想实验 1.1. 如果森林中的一棵树倒下&#xff0c;但周围没有人听到&#xff0c;那它是否会发出声音&#xff1f; 1.1.1. “贝克莱的树” 1.2. 主观唯心主义哲学家乔治贝克莱(George Berkeley)提出的&#xff0c;他认为“存在就是被感知” 1.2.1. 如果有人或有其他事物…...

用Promise实现util函数

有些时候&#xff0c;我们需要依赖于异步的返回结果做一些后续处理&#xff0c;until函数在这种场景下非常有用&#xff0c;你能实现它吗 ? 让我们来试试吧 &#x1f447;: <script setup langts> import { ref,watch } from "vue"const count ref(0)/*** I…...

使用numpy处理图片——白色背景变全透明

在《使用numpy处理图片——基础操作》一文中&#xff0c;我们通过对所有像素的alpha值做修改&#xff0c;让图片变成半透明。 我们看到本来是黑色的字体也因为半透明的原因变得颜色比较淡。 本文我们将判断每个像素的RGB值。如果是纯白底色&#xff0c;则将该像素的alpha值调…...

计算机网络层之ICMP与IGMP

计算机网络传输层协议有&#xff1a;tcp和udp&#xff0c;这两个接触最多&#xff0c;较为熟悉。除此之外&#xff0c;还有ICMP和IGMP&#xff0c;我们接触较少。 ICMP&#xff08;Internet Control Message Protocol&#xff09;和IGMP(Internet Group Management Protocol)是…...

FlinkAPI开发之自定义函数UDF

案例用到的测试数据请参考文章&#xff1a; Flink自定义Source模拟数据流 原文链接&#xff1a;https://blog.csdn.net/m0_52606060/article/details/135436048 概述 用户自定义函数&#xff08;user-defined function&#xff0c;UDF&#xff09;&#xff0c;即用户可以根据…...

阿里云国际服务器设置安全防护程序

阿里云云服务器&#xff08;ECS&#xff09;提供弹性、安全、高性能、高性价比的虚拟云服务器&#xff0c;满足您的所有需求。立即在这里免费注册&#xff01; 常见 Web 应用程序 请勿对 Web 服务控制台&#xff08;如 WDCP、TOMCAT、Apache、Nginx、Jekins、PHPMyAdmin、Web…...

C++获取内存使用情况

在程序编程过程中&#xff0c;为了防止出现内存泄漏情况出现&#xff0c;需要持续关注内存程序内存占用情况。如下方式实现获取当前进程内存使用情况&#xff1a; linux&#xff1a; void my_top(string path, bool flag) {if(flag){FILE* read_top fopen("/proc/self/…...

CRMEB多商户短信开发

在使用CRMEB多商户系统的时候&#xff0c;想要二开使用其他平台的短信&#xff0c;这里以阿里云短信为例的具体实现方法。 一、加载阿里云短信的SDK&#xff0c;执行命令&#xff1a;composer require alibabacloud/dysmsapi-20170525 二、增加阿里云短信的驱动 1.在 crmeb\…...

Leetcode 1049 最后一块石头的重量II

题意理解&#xff1a; 有一堆石头&#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合&#xff0c;从中选出任意两块石头&#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y&#xff0c;且 x < y。 思路转化&#xff1a;我们可…...

【设计模式之美】SOLID 原则之二:开闭原则方法论、开闭原则如何取舍

文章目录 一. 如何理解“对扩展开放、修改关闭”&#xff1f;二. 修改代码就意味着违背开闭原则吗&#xff1f;三. 如何做到“对扩展开放、修改关闭”&#xff1f;四. 如何在项目中灵活应用开闭原则&#xff1f; 一. 如何理解“对扩展开放、修改关闭”&#xff1f; 具体的说&a…...

Kafka 基本概念和术语

1、消息 Record&#xff1a;Kafka 是消息引擎嘛&#xff0c;这里的消息就是指 Kafka 处理的主要对象。 2、主题 Topic&#xff1a;主题是承载消息的逻辑容器&#xff0c;在实际使用中多用来区分具体的业务。在Kafka 中发布订阅的对象是 Topic。 3、分区 Partition&#xf…...

【每日面试题】Docker常见面试题精选

什么是Docker容器&#xff1f; Docker容器是一种轻量级的虚拟化技术&#xff0c;可以将应用及其依赖项打包在一个可移植的容器中&#xff0c;以便在多个环境中运行。 Docker镜像和容器之间有什么区别&#xff1f; Docker镜像是一个包含了应用程序及其依赖项的只读模板&#xf…...

uniapp项目怎么删除顶部导航栏

uniapp去掉顶部导航的方法&#xff1a; 1、去掉所有导航栏 "globalStyle": { "navigationBarTextStyle": "white", "navigationBarTitleText": "uni-app", "navigationBarBackgroundColor": "#007AFF"…...

m3u8视频下载终极指南:轻松获取加密流媒体内容的完整解决方案

m3u8视频下载终极指南&#xff1a;轻松获取加密流媒体内容的完整解决方案 【免费下载链接】m3u8_downloader 项目地址: https://gitcode.com/gh_mirrors/m3/m3u8_downloader 还在为无法保存在线视频而烦恼吗&#xff1f;m3u8_downloader项目为你提供了简单快速的解决方…...

优化TJpgDec在MM32F5微控制器上的图像解码性能 - 基于MindSDK的实践探索

1. TJpgDec在嵌入式系统中的独特价值 第一次接触TJpgDec是在三年前的一个智能家居项目里&#xff0c;当时需要在资源受限的STM32F407上实现图片显示功能。市面上常见的JPEG解码库要么体积庞大&#xff0c;要么对内存要求极高&#xff0c;直到发现了ChaN开发的这个轻量级解决方案…...

Jedi-vim与其他Vim插件的终极兼容性指南:避免冲突的10个技巧

Jedi-vim与其他Vim插件的终极兼容性指南&#xff1a;避免冲突的10个技巧 【免费下载链接】jedi-vim Using the jedi autocompletion library for VIM. 项目地址: https://gitcode.com/gh_mirrors/je/jedi-vim Jedi-vim是Vim编辑器中最强大的Python自动补全插件之一&…...

基于STM32的充电桩控制器设计(有完整资料)

资料查找方式&#xff1a;特纳斯电子&#xff08;电子校园网&#xff09;&#xff1a;搜索下面编号即可编号&#xff1a;T4532205M设计简介&#xff1a;本设计是基于单片机的充电桩控制器设计&#xff0c;主要实现以下功能&#xff1a;1、RFID可以注册卡以及删除卡&#xff0c;…...

暗黑3一键宏终极指南:D3keyHelper让你的刷图效率翻倍

暗黑3一键宏终极指南&#xff1a;D3keyHelper让你的刷图效率翻倍 【免费下载链接】D3keyHelper D3KeyHelper是一个有图形界面&#xff0c;可自定义配置的暗黑3鼠标宏工具。 项目地址: https://gitcode.com/gh_mirrors/d3/D3keyHelper 还在为暗黑3中重复的技能按键感到疲…...

res-downloader资源捕获完全指南:从证书配置到多平台资源下载的解决方案

res-downloader资源捕获完全指南&#xff1a;从证书配置到多平台资源下载的解决方案 【免费下载链接】res-downloader 视频号、小程序、抖音、快手、小红书、直播流、m3u8、酷狗、QQ音乐等常见网络资源下载! 项目地址: https://gitcode.com/GitHub_Trending/re/res-downloade…...

如何通过ImageToSTL实现图像三维化?解锁创意设计新可能

如何通过ImageToSTL实现图像三维化&#xff1f;解锁创意设计新可能 【免费下载链接】ImageToSTL This tool allows you to easily convert any image into a 3D print-ready STL model. The surface of the model will display the image when illuminated from the left side.…...

D3KeyHelper:如何通过智能操作优化解放暗黑3玩家双手的效率工具

D3KeyHelper&#xff1a;如何通过智能操作优化解放暗黑3玩家双手的效率工具 【免费下载链接】D3keyHelper D3KeyHelper是一个有图形界面&#xff0c;可自定义配置的暗黑3鼠标宏工具。 项目地址: https://gitcode.com/gh_mirrors/d3/D3keyHelper 一、问题场景&#xff1a…...

【车辆】插电式混合动力汽车(PHEV)动力系统进行建模与设计MATLAB 代码,含发动机、电机、电池组等组件

✅作者简介&#xff1a;热爱科研的Matlab仿真开发者&#xff0c;擅长毕业设计辅导、数学建模、数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。&#x1f447; 关注我领取海量matlab电子书和数学建模资料&#x1f34a;个人信条&#xff1a;格物致知,完整Matl…...

大模型工具调用乱斗:MCP协议凭什么火?实战踩坑与选型建议

大模型工具调用乱斗&#xff1a;MCP协议凭什么火&#xff1f;实战踩坑与选型建议 作者&#xff1a;戴维1号 来自&#xff1a;NEXUS Tech Curator&#xff08;https://www.lsn.org.cn) 开场&#xff1a;被"大模型有脑子没手"折磨的第 N 天 你有没有这种感觉——大模型…...