贪心算法day2(最长递增子序列)

embedded/2024/11/14 7:22:10/

目录

1.最长递增子序列

方法一:动态规划 

方法二:贪心+二分查找


1.最长递增子序列

链接:. - 力扣(LeetCode)

方法一:动态规划 

思路:我们定义dp[i]为最长递增子序列,那么dp[j]就是在小于i范围内的最长子序列,最长子序列最少为1,所以dp数组初始化为1.代码实行步骤如下:

这种情况下时间复杂度为O(n*2) ,空间复杂度为 O(n)

具体实现如下:

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

方法二:贪心+二分查找

思路:我们用数组来举个例子

第二种情况:(ret.get(mid) > nums[i])

这种情况下时间复杂度为nlogN(二分查找的时间复杂度为logN),空间复杂度为O(n)

代码: 

 public static int lengthOfLIS(int[] nums){int n = nums.length;ArrayList<Integer> ret = new ArrayList<>();ret.add(nums[0]);for (int i = 0; i < n; i++) {if(nums[i] > ret.get(ret.size() - 1)){ret.add(nums[i]);}else{int left = 0,right = ret.size() - 1;while(left < right){int mid = (left + right)/2;if(ret.get(mid) < nums[i]){left = mid + 1;}else{right = mid;}}ret.set(left,nums[i]);}}return ret.size();}


http://www.ppmy.cn/embedded/136474.html

相关文章

使用 AMD GPU 的 ChatGLM-6B 双语语言模型

Using the ChatGLM-6B bilingual language model with AMD GPUs — ROCm Blogs 2024 年 4 月 4 日&#xff0c;作者&#xff1a; Phillip Dang. ChatGLM-6B 是一个开源的中英双语语言模型&#xff0c;拥有 62 亿参数。它基于通用语言模型 (GLM) 架构&#xff0c;针对中文对话进…

深入解析ETL与ELT架构:数据集成技术的演进与发展

摘要&#xff1a;随着大数据时代的到来&#xff0c;数据集成成为企业信息化建设的重要环节。本文将深入探讨ETL与ELT两种架构&#xff0c;分析它们在数据处理、性能、可扩展性等方面的差异&#xff0c;为企业数据集成提供技术指导。 一、引言 在大数据时代&#xff0c;企业需要…

Hive操作库、操作表及数据仓库的简单介绍

数据仓库和数据库 数据库和数仓区别 数据库与数据仓库的区别实际讲的是OLTP与OLAP的区别 操作型处理(数据库)&#xff0c;叫联机事务处理OLTP&#xff08;On-Line Transaction Processing&#xff09;&#xff0c;也可以称面向用户交易的处理系统&#xff0c;它是针对具体业务…

【WRF理论第七期】WPS预处理

【WRF理论第七期】WPS预处理 运行WPS&#xff08;Running the WPS&#xff09;步骤1&#xff1a;Define model domains with geogrid步骤2&#xff1a;Extracting meteorological fields from GRIB files with ungrib步骤3&#xff1a;Horizontally interpolating meteorologic…

Spring Boot实现的工程认证计算机课程管理解决方案

1系统概述 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及&#xff0c;互联网成为人们查找信息的重要场所&#xff0c;二十一世纪是信息的时代&#xff0c;所以信息的管理显得特别重要。因此&#xff0c;使用计算机来管理基于工程教育认证的计算机课程管理平台的相…

Hive 的数据存储单元结构

按照数据的粒度顺序&#xff0c;数据存储单元数据被组织为&#xff1a; 数据库 Databases 数据表 Tables 分区 Partitions 桶或簇 Buckets (or Clusters) 数据库 Databases 与传统的关系型数据库一样&#xff0c;数据库是一个名称空间&#xff0c;作用是避免表、视图、分…

思考:linux Vi Vim 编辑器的简明原理,与快速用法之《 7 字真言 》@ “鱼爱返 说 温泉哦“ (**)

Linux vi/vim | 菜鸟教程 https://zhuanlan.zhihu.com/p/602675406 Linux Vim编辑器的基本使用_vim文本编辑器-CSDN博客 思考 1. 记忆公式&#xff1a; 按键操作的 7 字真言 1&#xff1a; "鱼爱返 说 温泉哦" v i Esc : wq ! ----------- 一般的简单…

高级java每日一道面试题-2024年10月31日-RabbitMQ篇-RabbitMQ中vhost的作用是什么?

如果有遗漏,评论区告诉我进行补充 面试官: RabbitMQ中vhost的作用是什么? 我回答: 在Java高级面试中&#xff0c;关于RabbitMQ中vhost&#xff08;虚拟主机&#xff09;的作用是一个重要且常见的考点。以下是对vhost的详细解释&#xff1a; 一、vhost的基本概念 vhost&am…