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

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

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

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

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...