当前位置: 首页 > 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;新加波管理大学…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...