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

【LeetCode: 剑指 Offer II 112. 最长递增路径 | 递归 | DFS | 深度优先遍历 | 记忆化缓存表】

在这里插入图片描述

🍎作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🍎座右铭:人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯🎯

在这里插入图片描述

目录

    • 题目链接
    • 题目描述
    • 求解思路&实现代码&运行结果
      • DFS
        • 求解思路
        • 实现代码
        • 运行结果
      • 记忆化缓存
        • 求解思路
        • 实现代码
        • 运行结果
    • 共勉

题目链接

剑指 Offer II 112. 最长递增路径
329. 矩阵中的最长递增路径

题目描述

给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。

对于每个单元格,你可以往上,下,左,右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。

在这里插入图片描述

在这里插入图片描述

提示:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231 - 1


求解思路&实现代码&运行结果

DFS

求解思路

  1. 该题目的求解思路比较简单,我们直接从给定数组中的每一个位置开始遍历,通过DFS的思想找到上、下、左、右中最长的递增路径,记录当前位置的最大长度。
  2. 因为我们遍历的是整个数组,从每一个位置开始,所以说我们最后还需要比较每一个位置的长度,找到最长的即可。

实现代码

实现代码的方式有很多,你可以在设计递归的时候将参数放到函数中,也可以将参数设置为成员变量都是可以的,甚至再求一些值的时候,你可以将最后的答案放到参数中,当然也可以将每一步的答案都进行返回,递归设置相应的返回值。方式有很多,大家选择自己最喜欢,最熟悉的方式即可。

class Solution {public int longestIncreasingPath(int[][] matrix) {int m=matrix.length,n=matrix[0].length;int max=Integer.MIN_VALUE;for(int i=0;i<m;i++){for(int j=0;j<n;j++){max=Math.max(max,process(i,j,m,n,matrix));}}return max;}public int process(int x,int y,int m,int n,int[][] matrix){int up=x>0&&matrix[x][y]<matrix[x-1][y]?process(x-1,y,m,n,matrix):0;int right=y<n-1&&matrix[x][y]<matrix[x][y+1]?process(x,y+1,m,n,matrix):0;int down=x<m-1&&matrix[x][y]<matrix[x+1][y]?process(x+1,y,m,n,matrix):0;int left=y>0&&matrix[x][y]<matrix[x][y-1]?process(x,y-1,m,n,matrix):0;return Math.max(Math.max(up,right),Math.max(down,left))+1;}
}

运行结果

我们可以看到时间超限了,不要紧,至少证明我们的思路是没有问题的,我们可以继续优化嘛。
在这里插入图片描述

记忆化缓存

求解思路

  1. 我们直接添加一个缓存表,避免一个结果会重复产生计算,如果我们之前计算过,此时直接返回就可以。

实现代码

class Solution {public int longestIncreasingPath(int[][] matrix) {int m=matrix.length,n=matrix[0].length;int[][] dp=new int[m][n];for(int i=0;i<m;i++){Arrays.fill(dp[i],-1);}int max=Integer.MIN_VALUE;for(int i=0;i<m;i++){for(int j=0;j<n;j++){max=Math.max(max,process(i,j,m,n,matrix,dp));}}return max;}public int process(int x,int y,int m,int n,int[][] matrix,int[][] dp){if(dp[x][y]!=-1) return dp[x][y];int up=x>0&&matrix[x][y]<matrix[x-1][y]?process(x-1,y,m,n,matrix,dp):0;int right=y<n-1&&matrix[x][y]<matrix[x][y+1]?process(x,y+1,m,n,matrix,dp):0;int down=x<m-1&&matrix[x][y]<matrix[x+1][y]?process(x+1,y,m,n,matrix,dp):0;int left=y>0&&matrix[x][y]<matrix[x][y-1]?process(x,y-1,m,n,matrix,dp):0;return dp[x][y]=Math.max(Math.max(up,right),Math.max(down,left))+1;}
}

运行结果

在这里插入图片描述

共勉

最后,我想送给大家一句一直激励我的座右铭,希望可以与大家共勉!
在这里插入图片描述

在这里插入图片描述

相关文章:

【LeetCode: 剑指 Offer II 112. 最长递增路径 | 递归 | DFS | 深度优先遍历 | 记忆化缓存表】

&#x1f34e;作者简介&#xff1a;硕风和炜&#xff0c;CSDN-Java领域新星创作者&#x1f3c6;&#xff0c;保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享&#x1f48e;&#x1f48e;&#x1f48e; &#x1f34e;座右…...

hive 入门 一般用于正式环境 修改元数据(二)

安装配置可参考 https://blog.csdn.net/weixin_43205308/article/details/130020674 1、如果启动过derby&#xff0c;最小初始化过 在安装路径下删除 derby.log metastore_db rm -rf derby.log metastore_db此处省略安装mysql数据库 2、配置MySQL 登录mysql mysql -uroot …...

在RedHat系统上使用firewall-cmd命令可以将端口打开

在RedHat系统上使用firewall-cmd命令可以将端口打开&#xff0c;具体操作如下&#xff1a; 首先&#xff0c;检查当前系统使用的防火墙服务&#xff0c;比如firewalld或iptables&#xff0c;使用以下命令&#xff1a; systemctl status firewalld # 检查firewalld服务 system…...

分享(五):免费可用的多种类 API 大全集合整理

前言 搜罗了各大平台整理了一波免费可以用的 API &#xff0c;有需要的收藏起来啦。 实名认证 运营商二要素 API &#xff1a;运营商校验此姓名、手机号码是否一致。 运营商三要素 API&#xff1a;运营商验证姓名、身份证号码、手机号码是否一致&#xff0c;返回验证结果称…...

8.1 假设验证的基本概念

学习目标&#xff1a; 要学习假设检验的基本概念&#xff0c;我会按照以下步骤进行&#xff1a; 了解假设检验的基本概念&#xff1a;假设检验是一种统计推断方法&#xff0c;用于判断某个假设是否成立。一般来说&#xff0c;假设检验包括原假设和备择假设两个假设&#xff0c…...

C语言基础

为了学习数据结构&#xff0c;整理一篇基础的C语言入门知识&#xff08;仅供自身学习用&#xff09; 条件运算符 语法&#xff1a;exp1 ? exp2 : exp3; exp1是条件表达式&#xff0c;如果结果为真&#xff0c;返回exp2 如果结果为假&#xff0c;返回exp3 if (a > b)max …...

Docker教程:如何将Helix QAC创建为一个容器并运行?

在这个Docker教程中&#xff0c;你将了解到如何将Helix QAC创建为一个容器化的镜像并运行。 Docker的基本定义是一个开源且流行的操作系统级虚拟化&#xff08;通常称为“容器化”&#xff09;技术&#xff0c;它是轻量级且可移植的&#xff0c;主要在Linux和Windows上运行。D…...

1676_MIT 6.828 xv6中的CPU alarm_资料翻译整理

全部学习汇总&#xff1a; GreyZhang/g_unix: some basic learning about unix operating system. (github.com) 我觉得看了几个MIT的课程之后让我觉得我的大学四年有点浪费时光&#xff0c;看起来MIT的课程的确是很有饱满度。 这里&#xff0c;再整理一份课程中的作业要求。 …...

记一次内存泄漏问题的排查

阶段一&#xff1a; 前段时间&#xff0c;突然发现服务在毫无征兆的情况下发生了重启。去看了一下容器退出的日志&#xff0c;发现内存利用率超过了100%&#xff0c;导致容器重启&#xff0c;进一步看了skyWalking&#xff0c;发现heap内存超了&#xff0c;当时只是简单的以为是…...

QML控件--Drawer

文章目录一、控件基本信息二、控件使用三、属性成员一、控件基本信息 Import Statement&#xff1a;import QtQuick.Controls 2.14 Since&#xff1a;Qt 5.7 Inherits&#xff1a;Popup 二、控件使用 Drawer&#xff1a;提供一个可以使用滑动手势打开和关闭的侧面板&#xff…...

PHY- PHY芯片概述

1 PHY概述 关于Internet Protocal的分层模型可以参考文章 :【Internet Protocal-OSI模型中的网络分层模型】,下面我们讲讲底层以太网控制器和收发器的知识。其主要是处理OSI模型中的物理层和链路层的事情。 在CAN/CANFD、FlexRay等总线中,有控制器Controller和收发器Transc…...

【C++】如何获取当前正在运行的函数的名称?

func、FUNCTION、__PRETTY_FUNCTION__的区别 常用获取函数名成的方法都有__func__、FUNCTION、PRETTY_FUNCTION。那么它们的区别是什么呢&#xff1f;   1) func、FUNCTION&#xff1a; 主要是获取函数的名称。   2) PRETTY_FUNCTION&#xff1a; 不仅能获取函数的名称&am…...

42.原型对象 prototype

目录 1 面向对象与面向过程 2 原型对象 prototype 3 在内置对象中添加方法 4 constructor 属性 5 实例对象原型 __proto__ 6 原型继承 7 原型链与instanceof 7.1 原型链 7.2 instanceof 8 案例-模态框 1 面向对象与面向过程 编程思想有 面向过程 与 面向…...

python 读写txt方法

​​​​​​​ 1. Python支持在程序中读写 txt文件。这里有两种方式&#xff1a; 方式一&#xff1a;使用 python内置函数&#xff0c;该函数将一个字符串的长度转换为与这个字符串长度相关的值。 例如&#xff1a;" readme"&#xff08;"r&#xff09;。 prin…...

香橙派pi5下,debian,docker19.03.9版本runc容器逃逸

在香橙派pi5下,debian,docker19.03.9版本下,安装系统后,启动docker,显示一切正常。 当加入k8s集群以后,可以正常连接到集群,node状态显示为ready。看起来一切正常。不过过一会之后,香橙派节点内存飙升,然后挂掉。重连失败,需要重启后才能重连。且swapoff -a命令执行…...

Thinkphp6.0中间件.上

本节课我们来学习一下中间件的用法&#xff0c;定义一下中间件。 一&#xff0e;定义中间件 1. 中间件的主要用于拦截和过滤 HTTP 请求&#xff0c;并进行相应处理&#xff1b; 2. 这些请求的功能可以是 URL 重定向、权限验证等等&#xff1b; 3. 为了进一步了解中间件的用法&…...

十进制到八进制的转换

目录 十进制到八进制的转换 程序设计 程序分析 十进制到八进制的转换 【问题描述】对于输入的任意一个非负十进制整数n(0=<n<100000),打印输出与其等值的八进制数 【输入形式】非负十进制整数 【输出形式】相应十进制整数转换后的八进制正整数,若输入不符合要求,…...

【从零开始学Skynet】基础篇(四):网络模块常用API

游戏服务端要处理客户端请求&#xff0c;作为服务端引擎&#xff0c;网络编程也是Skynet的核心功能。1、学习网络模块 skynet.socket模块提供了网络编程的API&#xff0c;常用的API如下表所示&#xff1a;Lua API说明socket.listen(address ,port)监听一个端口&#xff0c;返回…...

怎么免费制作logo?logo免费设计在线生成,从此设计不求人

你有没有因为Logo制作而烦恼过&#xff1f;对于很多人来说&#xff0c;logo制作是一项比较大的工程&#xff0c;需要专门的设计师才能完成。但是请人设计费用高还很费时间&#xff0c;还需多次沟通修改。其实&#xff0c;我们可以自己免费制作logo&#xff0c;下面&#xff0c;…...

【目标检测】目标检测遇上知识图谱:Object detection meets knowledge graphs论文解读与复现

前言 常规的目标检测往往是根据图像的特征来捕捉出目标信息&#xff0c;那么是否有办法加入一些先验信息来提升目标检测的精准度&#xff1f; 一种可行的思路是在目标检测的输出加入目标之间的关联信息&#xff0c;从而对目标进行干涉。 2017年8月&#xff0c;新加波管理大学…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...