【LeetCode: 300. 最长递增子序列 | 暴力递归=>记忆化搜索=>动态规划】

news/2024/4/25 0:22:57/

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述

🍔 目录

    • 🚩 题目链接
    • ⛲ 题目描述
    • 🌟 求解思路&实现代码&运行结果
      • ⚡ 暴力递归1
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
      • ⚡ 暴力递归2
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
      • ⚡ 记忆化搜索
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
      • ⚡ 动态规划
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
      • ⚡ 动态规划 + 二分查找
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
    • 💬 共勉

🚩 题目链接

  • 300. 最长递增子序列

⛲ 题目描述

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1:

输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:

输入:nums = [0,1,0,3,2,3]
输出:4
示例 3:

输入:nums = [7,7,7,7,7,7,7]
输出:1

提示:

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

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


⚡ 暴力递归1

🥦 求解思路

  1. 根据题目的意思,让我们求得最长递增子序列的长度是什么,我们可以设计这样一个递归函数,从某一个位置开始,如果当前选择的数字是大于我们之前选择的数字的,那么我们记录长度的变量++,否则,进行下一个位置的判断,之前选择的数不变,记录长度的也不变。
  2. 接下来我们来看一下具体代码的实现。

🥦 实现代码

class Solution {public int lengthOfLIS(int[] nums) {return process(0,nums,0,Integer.MIN_VALUE);}public int process(int index,int[] nums,int cnt,int pre){if(index==nums.length){return cnt;}int max=Integer.MIN_VALUE;for(int i=index;i<nums.length;i++){if(nums[i]>pre){max=Math.max(max,process(i+1,nums,cnt+1,nums[i]));}else{max=Math.max(max,process(i+1,nums,cnt,pre));}}return max;}
}

🥦 运行结果

时间超限,使我们期待的结果!!!
在这里插入图片描述


⚡ 暴力递归2

🥦 求解思路

  1. 上面虽然实现了一个递归版本的题解,时间超限了,是我们期待的结果,但是并不是一个好的递归版本,因为状态参数太多了,不方便都维护。
  2. 接下来我们就再来想一想,还有没有可能设计一个更好的递归函数呢?
  3. 我们可以设计这样一个递归函数,以当前index位置为结尾,递归函数中每次从0到index-1的位置进行选择,如果存在元素小于当前index位置的元素,继续递归调用,下一个位置从当前小于index位置开始,重复该过程,直至结束。
  4. 我们可以看到,这个递归函数比起我们上面设计的递归函数精简不少,接下来我们就来一起看一下具体的实现。

🥦 实现代码

class Solution {public int lengthOfLIS(int[] nums) {int max=Integer.MIN_VALUE;for(int i=0;i<nums.length;i++){max=Math.max(max,process(i,nums));}return max;}public int process(int index,int[] nums){if(index==nums.length){return 0;}int max=1;for(int i=0;i<index;i++){if(nums[i]<nums[index]){max=Math.max(max,process(i,nums)+1);}}return max;}
}

🥦 运行结果

在这里插入图片描述


⚡ 记忆化搜索

🥦 求解思路

  1. 根据我们递归的分析,在递归的过程中会产生重复的子过程,所以我们想到了加一个缓存表,也就是我们的记忆化搜索。

🥦 实现代码

class Solution {public int lengthOfLIS(int[] nums) {int max=Integer.MIN_VALUE;int n=nums.length;int[] dp=new int[n];Arrays.fill(dp,1);for(int i=0;i<n;i++){max=Math.max(max,process(i,nums,dp));}return max;}public int process(int index,int[] nums,int[] dp){if(index==nums.length){return 0;}if(dp[index]!=1) return dp[index];int max=1;for(int i=index;i<nums.length;i++){if(nums[i]>nums[index]){max=Math.max(max,process(i,nums,dp)+1);}}return dp[index]=max;}
}

🥦 运行结果

在这里插入图片描述


⚡ 动态规划

🥦 求解思路

  1. 按照我们之前递归和记忆化搜索的思路,通过动态规划实现出来。

🥦 实现代码

class Solution {public int lengthOfLIS(int[] nums) {int n=nums.length;int[] dp=new int[n];int max=0;Arrays.fill(dp,1);for(int index=n-1;index>=0;index--){for(int i=index;i<n;i++){if(nums[i]>nums[index]){dp[index]=Math.max(dp[index],dp[i]+1);}}max=Math.max(max,dp[index]);}return max;}
}

🥦 运行结果

在这里插入图片描述


⚡ 动态规划 + 二分查找

🥦 求解思路

  1. 因为题目要我们查找的是递增子序列,也就是元素按照严格递增排列的,所以我们可以想到使用二分来进行优化。
  2. 我们将每次查找的结果放到开辟的数组空间中,具体怎么做呢?
  3. 我们可以每次遍历我们nums中的数字x,然后在收集数组的区间内进行查找大于当前x做左侧的位置,最后将该位置设置为x;
  4. 如果此时查找的边界到达了我们此时数组下标位置,说明此时该元素是大于数组中所有元素的,此时数组下标位置继续向右移动。

🥦 实现代码

class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];int res = 0;for (int x : nums) {int left = -1, right = res;while(left+1 < right){int mid = left + ((right - left) >> 1);if(dp[mid] < x){left = mid;}else{right = mid;}}dp[right] = x;if(right == res){res++;}}return res;}
}

🥦 运行结果

在这里插入图片描述


💬 共勉

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

在这里插入图片描述


http://www.ppmy.cn/news/46968.html

相关文章

E4--光纤接口通信测试应用2023-04-17

1.场景 使用两块开发板A和B&#xff0c;通过光纤接口将在A板上ROM中存储的图片数据转发到B板并显示在B板连接的显示屏上&#xff0c;实现光纤接口通信。 具体场景是&#xff0c;由于A735T片上资源有限&#xff0c;因此ROM IP存储了一张1024*600&#xff08;LVDS屏幕&#xff0…

基于html+css的盒子展示6

准备项目 项目开发工具 Visual Studio Code 1.44.2 版本: 1.44.2 提交: ff915844119ce9485abfe8aa9076ec76b5300ddd 日期: 2020-04-16T16:36:23.138Z Electron: 7.1.11 Chrome: 78.0.3904.130 Node.js: 12.8.1 V8: 7.8.279.23-electron.0 OS: Windows_NT x64 10.0.19044 项目…

用英语翻译中文-汉字英文翻译

中文转英语翻译 作为一款高效、准确的中文转英语翻译软件&#xff0c;我们的产品可以帮助全球用户更好地沟通和合作&#xff0c;实现跨文化交流。 在全球化的今天&#xff0c;中英文翻译已经成为商务、学术、娱乐等各个领域不可或缺的一部分。我们的中文转英语翻译软件是为了…

C++初阶之缺省参数

目录 前言 缺省参数 1.缺省参数的概念 2.缺省参数的分类 全缺省参数 半缺省参数 前言 今天小编继续给大家带来C的内容&#xff0c;那么今天小编给大家讲解的就是有关C中缺省参数的介绍。 缺省参数 1.缺省参数的概念 缺省参数是声明或定义函数时为函数的参数指定一个缺省…

实验一 表的建立、修改和删除

实验一 表的建立、修改和删除 第1关&#xff1a;创建表 任务描述 本关任务&#xff1a;要求学生创建Student&#xff0c;Course&#xff0c;SC表 相关知识 使用SQL语言中的create table语句。 SQL语句中关键字大小写不区分。 create table Student (Sno char(10) primary…

138. 复制带随机指针的链表

给你一个长度为 n 的链表&#xff0c;每个节点包含一个额外增加的随机指针 random &#xff0c;该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成&#xff0c;其中每个新节点的值都设为其对应的原节点的值。新节点的 n…

【牛客网】树根与星际密码

目录 一、编程题 1.树根 2.星际密码 二、选择题 一、编程题 1.树根 链接&#xff1a;数根__牛客网 (nowcoder.com) 数根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数&#xff0c;那么这个数就是数根&#xff1b;如果结果是两位数或者包括更多位的数…

换个角度使用Redis去解决跨域存取Session问题

系列文章目录 Redis缓存穿透、击穿、雪崩问题及解决方法 Spring Cache的使用–快速上手篇 分页查询–Java项目实战篇 全局异常处理–Java实战项目篇 该系列文章持续更新&#xff0c;更多的文章请点击我的主页查看哦&#xff01; 文章目录 系列文章目录前言一、遇到的情况二、解…

【论文总结】V-Shuttle:可扩展和语义感知的 Hypervisor 虚拟设备模糊测试

介绍 这是来自2021 CCS的一篇论文&#xff0c;作者有GaoningPan, Xingwei Lin, Xuhong Zhang, Yongkang Jia, Shouling Ji, Chunming Wu, Xinlei Ying, Jiashui Wang, Yanjun Wu。该论文提出V-shuttle的新框架来执行管控程序的模糊测试&#xff0c;该框架执行可扩展和语义感知…

AVL树(C++实现)

文章目录 AVL树的概念AVL树结点定义AVL树的插入AVL树的旋转左单旋右单旋左右单旋右左双旋 AVL树的验证AVL树的性能AVL树及测试完整代码 AVL树的概念 二叉搜索树虽然可以缩短查找的效率,但如果数据有序或接近有序,那么二叉搜索树将退化为单支树,查找元素则相当于在顺序表中搜索…

WHOIS查询参考:域名注册信息的含义

以下详细说明了域名的域名所有者、管理联系人、技术联系人、付费联系人等信息的中英文含义。为注册域名和whois查询提供参考。 域名所有者注册信息含义 域名所有者&#xff08;Registrant&#xff09;是指域名属于谁&#xff0c;用于判定域名所有权。域名所有者可以是单位企业…

C语言实现顺序表--数据结构

魔王的介绍&#xff1a;&#x1f636;‍&#x1f32b;️一名双非本科大一小白。魔王的目标&#xff1a;&#x1f92f;努力赶上周围卷王的脚步。魔王的主页&#xff1a;&#x1f525;&#x1f525;&#x1f525;大魔王.&#x1f525;&#x1f525;&#x1f525; ❤️‍&#x1…

如何使用Tensorflow神经网络模型来完成兰州房价预测分析?

兰州房价预测是一个非常热门的话题,许多人都对如何预测兰州房价感兴趣。在本文中,我将介绍如何使用TensorFlow来预测兰州房价,并提供Python源代码。 首先,我们需要收集兰州的房价数据。我们可以从房地产网站或政府统计数据中获取。在本文中,我们将使用Kaggle上提供的兰州…

收音机知识,调谐(选频/滤波),调制(升频)

参考&#xff1a;https://www.bilibili.com/video/BV1d14y1N7nm/?spm_id_from333.999.0.0&vd_source00bd76f9d6dc090461cddd9f0deb2d51 有关知识提纲 整个信号的传输变化调谐人耳听到声音的频率范围&#xff08;20~20000Hz&#xff09;天线和传送信号的波长关系波长和天线…

RHCE第一次作业at和cront两个任务管理程序的区别

1.at 单一执行的例行性工作&#xff1a;仅处理执行一次就结束了 -m 当任务完成之后&#xff0c;即使没有标准输出&#xff0c;将给用户发送邮件 -l atq的别名&#xff0c;可列出目前系统上面的所有该用户的at调度 -d atrm的别名,可以取消一个在at调度中的工作 -v 使用较明显的…

pandas中df.groupby详解?

df.groupby 是 pandas 库用于实现按照某些列进行拆分&#xff0c;应用函数和组合的一个功能。步骤如下&#xff1a; 1. 按照指定的一列或多列进行分组 (grouping) 2. 对每个分组应用一个聚合函数 (aggregation) 3. 将每个分组的聚合结果合并成一个数据结构 语法&#xff1a; df…

Session详解(重点)

类似于去服务器注册账号&#xff0c;只要服务器不停机&#xff0c;自己注册的账号一直会存在服务器。 什么是Session&#xff1a; 1.服务器会给每一个用户&#xff08;浏览器&#xff09;创建一个对象&#xff1b; 2.一个Session独占一个浏览器&#xff0c;只要浏览器没有关…

***大论文中插入Visio不失真方法:word插入viso图片方法

***大论文中插入Visio不失真方法&#xff1a;word插入viso图片方法 1、可以直接导出emf2、如果利用emf导致字符间距过大&#xff0c;可以选择下面方式 1、可以直接导出emf 导出emf方法&#xff1a; 打开visio --> 另存为 --> 选择emf格式文件 打开word --> 插入图片…

[API]ListList方法集合排序Lambda表达式(四)

List接口&#xff1a; 继承自Collection接口&#xff0c;List集合是可重复集合&#xff0c;并且有序&#xff0c;还提供了一套可以通过下标来操作元素的方法 常见的实现类&#xff1a; ArrayList&#xff1a;内部使用数组实现&#xff0c;查询性能更好(直接下标找到物理地址)、…

开源GPT-4小羊驼(Vicuna)快速上手指南

小羊驼&#xff08;Vicuna)是什么 Vicuna: 一个开源的GPT&#xff0c;宣称实现了GPT-4 90%的功能。 UC伯克利学者联手CMU、斯坦福等&#xff0c;再次推出一个全新模型70亿/130亿参数的Vicuna&#xff0c;俗称「小羊驼」&#xff08;骆马&#xff09;。 并且和其他以往不同的是…